Manacher算法【用于求解字符串中最长回文子串的问题】

Love The Way You Lie 2023-09-25 14:16 104阅读 0赞

## [Manacher][]算法 ##

**描述：** Manacher 算法用于求解字符串中[最长回文子串][Link 1]的问题。

在了解该算法之前需要明白一些基本概念：

*  回文串：对于字符串s ss，s = s r e v s = s\_\{rev\}s=srev，即s ss等于s ss的逆序，则s ss是一个回文串
 *  回文串分为奇回文串以及偶回文串

**解法**：直观的暴力做法时间复杂度为O ( n 3 ) O(n^3)O(n3)，即枚举所有的子串，对这些子串判断是否回文。

稍加思考便会发现，对于一个[回文串][Link 2]，他一定有一个对称中心点，这个点的左右两边是相同的，如果按照对称中心来依次枚举，那么复杂度为变为O ( n 2 ) O(n^2)O(n2)

### 算法思想 ###

Manacher算法实际上就是对枚举对称中心这一做法的优化。

字符个数的奇偶性不同，对称中心也是不同的，例如对于奇回文串a b a abaaba，对称中心点为b bb，对于偶回文串a b b a abbaabba，对称中心点则为b b bbbb中间，为了统一对称点，一般的做法是，将原字符串s ss的首尾以及相邻的两个字符中间插入一个不会出现的字符（例如：\#）这样会统一成一个奇回文串，新字符串长度 = 原串 \* 2 + 1

例如原串：a b b a abbaabba

新字符串：∗ a ∗ b ∗ b ∗ a ∗ \*a\*b\*b\*a\*∗a∗b∗b∗a∗

--------------------

考虑维护一个数组：L LL

其中L \[ i \] L\[i\]L\[i\]表示以i ii为对称中心的最长回文串的最右边的字符到s \[ i \] s\[i\]s\[i\]的长度（即回文半径）

对于原串：a a b a b aababaabab，添加一个字符变为∗ a ∗ a ∗ b ∗ a ∗ b ∗ \*a\*a\*b\*a\*b\*∗a∗a∗b∗a∗b∗，他的L LL数组如下：

![26a545d2d1fc25e8f2e7d3c19212f179.png][]

L LL数组的作用：L \[ i \] − 1 L\[i\]-1L\[i\]−1可以表示该子串在原串中对应的回文串的长度，例如上面图片中b bb的L LL值为4，那么原串a a b a b aababaabab中，以b bb为对称中心的回文串长度为4 − 1 = 3 4-1=34−1=3

因此，只需要找到所有的L LL数组就可以求出最长回文串了。

--------------------

### 求L LL数组 ###

假定要求位置i ii的L LL数组，(i ii之前的已经求出)，我们考虑维护两个值k kk, r rr。其中r rr表示，i ii之前所有位置求出来的右端点的最大值（即L LL数组的最大值），k kk表示r rr最大时的位置。

那么可以分为以下情况讨论

1、i < r i < ri<r时

![f2f1a6e07c88010088fb32bd0b6c50c5.png][]

如上图所示，其中红色和橙色部分是相同的，找到i ii关于k kk的对称位置，即j jj（其中j = 2 ∗ k − i j = 2\*k-ij=2∗k−i ），由于k kk是对称中心位置，那么判断一下L \[ j \] L\[j\]L\[j\]与r − i r-ir−i的大小关系

*  l \[ j \] < r − i l\[j\]<r-il\[j\]<r−i如下图所示：
    
    ![9c99762d7a41d045f559f7b1be27314b.png][]
    
    绿色部分必定相同，因此l \[ i \] = l \[ j \] l\[i\] = l\[j\]l\[i\]=l\[j\]
 *  l \[ j \] > r − i l\[j\] > r-il\[j\]>r−i
    
    此时，l \[ i \] > = r − i l\[i\] >= r-il\[i\]>=r−i的，超出的部分，需要暴力更新。

2、i > r i>ri>r时

没有可以使用的信息，直接暴力更新即可。

注意：记得更新k , r k,rk,r的值。

一些技巧：可以在字符串首尾放置两个"哨兵"，它们和其他字符串均不同，这样暴力更新时不用考虑边界问题

//其中s[0]='@',s[n]='%',中间插入的字符为'#'
    
    int ans = 0, k = 0, r = 0;
        l[1] = 1;
        for (int i = 2; i <= n; i ++) {
            if (i < r) l[i] = min (r - i, l[(k << 1) - i]);
            else l[i] = 1;
    
            while (s[i - l[i]] == s[i + l[i]]) l[i] ++; // 暴力更新超过r的部分
            if (i + l[i] > r) k = i, r = i + l[i]; // 更新k,r
            ans = max (ans, l[i] - 1); // 找到最长回文子串
        }
        cout << ans << endl;

*  1
 *  2
 *  3
 *  4
 *  5
 *  6
 *  7
 *  8
 *  9
 *  10
 *  11
 *  12
 *  13

--------------------

### 例题 ###

**题目描述**

https://www.luogu.com.cn/problem/P3805

给出一个只由小写英文字符 a , b , c , … y , z \\texttt a,\\texttt b,\\texttt c,\\ldots\\texttt y,\\texttt za,b,c,…y,z 组成的字符串 S ,求 S 中最长回文串的长度 。

字符串长度为 n。

**输入格式**

一行小写英文字符 a , b , c , ⋯   , y , z \\texttt a,\\texttt b,\\texttt c,\\cdots,\\texttt y,\\texttt za,b,c,⋯,y,z 组成的字符串 S。

**输出格式**

一个整数表示答案。

**输入样例**

aaa

*  1

**输出样例**

*  1

**说明/提示**

1 ≤ n ≤ 1.1 × 1 0 7 1\\le n\\le 1.1\\times 10^71≤n≤1.1×107。

**参考程序**

#include <iostream>
    #include <cstring>
    
    using namespace std;
    
    const int N = 2e7 + 2e6;
    
    string t, s;
    int n, m;
    int l[N];
    
    
    int main () {
        cin >> t;
        m = t.length();
        n = (m << 1) + 1;
        s.resize(n + 1);
        s[0] = '@', s[n] = '%', s[1] = '#';
        for (int i = 1; i <= m; i ++) {
            s[i << 1] = t[i - 1];
            s[i << 1 | 1] = '#';
        }
    
        int ans = 0, k = 0, r = 0;
        l[1] = 1;
        for (int i = 2; i <= n; i ++) {
            if (i < r) l[i] = min (r - i, l[(k << 1) - i]);
            else l[i] = 1;
    
            while (s[i - l[i]] == s[i + l[i]]) l[i] ++;
            if (i + l[i] > r) k = i, r = i + l[i];
            ans = max (ans, l[i] - 1);
        }
        cout << ans << endl;
        return 0;
    }

[Manacher算法\_Psycho social的博客-CSDN博客\_manacher算法][Manacher_Psycho social_-CSDN_manacher]

[Manacher算法的详细讲解 - 简书][Manacher_ -]

[Manacher算法 - 大嘤熊 - 博客园][Manacher_ - _ -]

[【数据结构】Manacher算法\_◎六音弦的博客-CSDN博客\_manacher算法][Manacher_-CSDN_manacher]

[Manacher]: https://so.csdn.net/so/search?q=Manacher&spm=1001.2101.3001.7020
[Link 1]: https://so.csdn.net/so/search?q=%E6%9C%80%E9%95%BF%E5%9B%9E%E6%96%87%E5%AD%90%E4%B8%B2&spm=1001.2101.3001.7020
[Link 2]: https://so.csdn.net/so/search?q=%E5%9B%9E%E6%96%87%E4%B8%B2&spm=1001.2101.3001.7020
[26a545d2d1fc25e8f2e7d3c19212f179.png]: https://img-blog.csdnimg.cn/img_convert/26a545d2d1fc25e8f2e7d3c19212f179.png
[f2f1a6e07c88010088fb32bd0b6c50c5.png]: https://img-blog.csdnimg.cn/img_convert/f2f1a6e07c88010088fb32bd0b6c50c5.png
[9c99762d7a41d045f559f7b1be27314b.png]: https://img-blog.csdnimg.cn/img_convert/9c99762d7a41d045f559f7b1be27314b.png
[Manacher_Psycho social_-CSDN_manacher]: https://blog.csdn.net/weixin_43501684/article/details/124325764
[Manacher_ -]: https://www.jianshu.com/p/116aa58b7d81
[Manacher_ - _ -]: https://www.cnblogs.com/jiezao/p/13528782.html
[Manacher_-CSDN_manacher]: https://blog.csdn.net/Memoy0517/article/details/124556094