【字符串】Manacher

更新于 分类于 ， 阅读次数： 本文字数： 3.5k 阅读时长 ≈ 3 分钟

Manacher（马拉车算法），当初按教学稿写的，应该还比较详细

引入

给定一个字符串，如何判断它是不是回文串？

根据定义写出朴素算法：枚举可能成为回文串对称中心（奇偶）的位置，从中间向两边找，如果两边是不同字符说明不是回文串。

给定一个字符串，如何找出它所有的回文子串？

枚举每一个子串，判断它是否为回文子串。枚举花费O(n2)O(n^2) 。

时间复杂度太高，如何优化？

考虑回文串的特点。

观察如下两个回文串：

  • 回文串abccba：得到信息？bccb 也是回文串，cc也是回文串，以两个c 中间位置为中心最长可以延展长为66 的回文串。
  • 回文串abcba：得到信息？bcb 也是回文串，c 也是回文串，以c 为中心最长可以延展长为55 的回文串。

结论（非证明）：一个回文串的，每一个关于该回文串中心对称的子串，都是回文串。

基于此，一个字符串，我们延展每一个字符（奇数长度回文串的中心）和每一个空位（偶数长度回文串的中心），去找以它为中心的最长回文串，就可以得到字符串所有的回文子串的信息。

复杂度仍然不友好。

继续观察回文串的特点。

考虑回文串abaccaba，按以上的说法，我们先发现以左边的b可以延伸最长aba回文串，我们随后发现以cc为重心最长沿伸abaccaba回文串，而根据回文串的特点，我们已经可以判断，必有以右边的b为重心的aba回文串。

即，我们考虑，回文串中的回文串能给我们什么信息？

给出一些记号：

  • 为方便奇偶统一处理，在每两个字符中间插入一个奇怪的特殊符号，比如S="abccba" 我们将其转变为Ma="$#a#b#c#c#b#a#\0"
  • 记Mp[i]Mp[i] 为字符串第ii 个字符为中心可以延展的最长回文串半径长度
  • 记mxmx 为延展回文串时访问到的最右端字符位置，idid 为mxmx 对应的那趟延展的回文串的中心位置

扫一遍字符串，考虑当前正在第ii 个字符，想获取以它为中心的回文串的信息Mp[i]Mp[i] ：

  • 若mx≤imx\leq i ，以ii 为中心的潜在回文串，与先前获知的任何回文串都没有关系，当前已知的所有回文串都不能给我们提供任何跟Mp[i]Mp[i] 有关的信息，那么只能朴素的由ii 为中心向两边延伸，自己去获取信息。
  • 若id<i<mxid<i<mx ，联想上面的例子，ii 在一个已知的回文串内，它有对称点k=2⋅id−ik=2\cdot id-i

根据上面的观察，我们想当然的希望Mp[i]=Mp[k]Mp[i]=Mp[k] ，这样就可以省去Mp[k]Mp[k] 长度的沿伸代价，但是这个结论成立吗？

  • 若Mp[k]>mx−iMp[k]>mx-i ：

以kk 为中心延展超出当前(id,mx)(id,mx) 回文串的部分，是不能提供任何信息的，我们不知道(id,mx)(id,mx) 串的左右是什么样子，因此我们只能得到kk 或ii 为中心，延展mx−imx-i 长度的部分（即红框部分）一定是回文串。

  • 若Mp[k]≤mx−iMp[k]\leq mx-i ：

由于在大回文串内，我们显然可以得到以ii 为中心一定能够沿伸Mp[k]Mp[k] 长度的回文串。

综上，id<i<mxid<i<mx 时，依靠对称点k=2⋅id−ik=2\cdot id-i ，我们得知以ii 为中心一定能够沿伸min⁡(Mp[k],mx−i)\min(Mp[k],mx-i) 长度的回文串，接着min⁡(Mp[k],mx−i)\min(Mp[k],mx-i) 长度继续向外沿伸判断回文串即可。

马拉车

  • 作用：找出字符串里所有回文串
  • 暴力回文：O(n2)O(n^2) ，枚举回文中心后向外拓展，根据上述原理进行改进。
  • 记法同上：
    • 偶数和奇数长度的回文字符须不同处理，因此在每个字符中间插入一个特殊符号，方便统一处理
    • 记Mp[i]Mp[i]​ 为ii​ 点能扩展出的最长回文长度，mxmx​ 为目前访问到过（找回文串）的最右字符位置，idid​ 为该回文串的对称中心位置。
  • 从首位遍历字符串，循环变量为ii​​ ，初始 idid​​ 置11​ ；
  • 在上述原理对应的过程中，ii​ 必然在idid​​ 右边，因此不需要考虑i<idi<id 的情况。
    • 当id<i<mxid<i<mx 时， ii 关于idid 的对称点为j=2×id−ij=2\times id-i , 可以得到Mp[i]≥min⁡(Mp[j],mx−i)Mp[i] \geq \min(Mp[j], mx-i) ，以Mp[i]=min⁡(Mp[j],mx−i)Mp[i]=\min(Mp[j], mx-i) 为半径，以ii 为中心向两边沿伸（省去[1,min⁡(Mp[j],mx−i)[1,\min(Mp[j], mx-i) 长度的沿伸）判断回文串，同步更新Mp[i]Mp[i] 。
    • 当i>=mxi>=mx​ 时，右边的情况未知，只能以ii​ 为中心，从半径11 开始向外沿伸判断回文串
  • 延展完成后，如果最右边界i+Mp[i]>mxi+Mp[i]> mx ，则更新mx=i+Mp[i],id=imx=i+Mp[i], id=i 。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
/* luoguP3805 */
/** Manacher **/
/**
 *给小写字符串，长度11e6内
 *求最长回文串长度
 **/
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1e7+1e6+10;
char str[N];
char Ma[N<<1]; //存储预处理过的字符串
int Mp[N<<1]; //Mp[i]表示某位置延展的最长回文串半径
void Manacher(char str[],int len) { //C风格字符串，len是该字符串长度
    //预处理
    int l=0;
    Ma[l++]='$';
    Ma[l++]='#';
    for(int i=0;i<len;i++) {
        Ma[l++]=str[i];
        Ma[l++]='#';
    } 
    Ma[l]=0;
    //算法主体，注意，为了代码更好写，这里的Mp[i]是实际最长回文半径+1
    int mx=0,id=0; //mx, id置初始值
    for(int i=1;i<l;i++) {
        if(i>=mx) Mp[i]=1; //目前延展最远的回文串不能提供有效信息
        else Mp[i]=min(Mp[(id<<1)-i],mx-i); //用对称点的回文半径更新Mp[i]
        while(Ma[i+Mp[i]]==Ma[i-Mp[i]]) Mp[i]++; //半径从Mp[i]开始延展直到遇见到不相等字符
        if(i+Mp[i]>mx) { //如果从i向右找回文串找到的最远位置已经超过了mx，更新mx和id
            mx=i+Mp[i]; //当前中心+最远半径
            id=i; //当前中心
        }
    }
}
int main()
{
    scanf("%s",str);
    int len=strlen(str);
    Manacher(str,len);
    int ans=0;
    for(int i=0;i<(len<<1)+2;i++)
        ans=max(ans,Mp[i]-1);
    printf("%d",ans);
    return 0;
}