manacher 算法详解

先上模板：P3805。

题意就是给你一个子串，然后求它的最大回文子串。

做法一

显然可以先 \(O(n^2)\) 枚举所有子串，再 \(O(n)\) 判断这个子串是否是回文串。

如果回文串都不会判断请左转 P1015。

这个算法时间复杂度 \(O(n^3)\)。

然后瞟了一眼数据范围和时限……

得 T 飞啊 qaq。

做法二

改进一下判断方法。

对于每个字符，找到子串内和它对称的字符，判断它们是否相同。

话说对称是什么意思呢？

回顾一下回文串的定义：

“回文串”是一个正读和反读都一样的字符串。--百度百科

对于一个字符，对于字符串反读后的位置相对应的字符，就是它的对称字符。

所以只要这个字符串内的所有相对称的字符都一样，那么这个字符串就是回文串了。

但是只有一个不同，就不是回文串。

比如说对于这个字符串：

soulistakioi

它的反读字符串：

ioikatsiluos

就可以知道第一个 's' 与最后一个 'i' 对称，第二个 'o' 与倒数第二个 'o' 对称……以此类推。

这个算法时间复杂度还是 \(O(n^3)\)。

但是常数小了一点。

做法三

举个栗子先：

babdbdbac

我们在判断中间的 dbd 的过程时，会发现对称字符 d 和 d 相同。

然而在判断 'bdbdb' 时，发现又会碰到这个 d 和 'd'！

那我们何不利用这个之前已经计算过的信息呢？

说句题外话。既然有了对称字符，那么是不是有对称轴呢？

其实很简单，就是中间的那个点，我们叫它对称中心。

比如这个串：

tygzakioi

那么那个 'a' 就是它的对称中心了。

不过有个问题，比如之前的那个串：

soulistakioi

它的字符个数是偶数，所以对称中心是 's' 和 't' 中间的那条缝，这让我们枚举的时候很不好处理。

所以我们可以在两个字符中插入一个 '|'，变成下面这样：

|s|o|u|l|i|s|t|a|k|i|o|i|

这样这个串的对称中心就是 's' 和 't' 中间的 '|' 了。

（当然处理方法有很多，比如 OI Wiki 中的分类讨论，看个人喜好吧）

发现一个串的一对对称字符到它的对称中心距离相等。

那么设其中一个字符位置为 \(j\)，对称中心为 \(i\)，那么它的对称的点的位置为 \(2i-j\)。

下面用的很多，会推的自己推一下，不会推的先记下来。

我们定义回文半径是回文串中对称中心到两端的距离。（那端都可以，反正都一样）

比如这个串：

acabaca

它的回文半径是 3。（当然你想当成 4 也可以，看个人喜好，但下面的结论要微改一下）

由于上面的一波操作，所有的回文串都变成奇数长度了，所以一个回文串的回文半径就是它的长度减一再除以二。

然后惊喜地发现，一个回文串中除去 '|' 的长度也是原串的长度减一再除以二。

所以一个回文串中的有效字符（即非 '|'）数量就是它的回文半径。

接下来我们会发现两个子串会出现上面的情况，当且仅当它们对称中心在同一个位置。（感性理解一下，简而言之我懒得证）

回忆起上面的几句话：

所以只要这个字符串内的所有相对称的字符都一样，那么这个字符串就是回文串了。
但是只有一个不同，就不是回文串。
发现一个串的一对对称字符到它的对称中心距离相等。

所以我们可以枚举对称中心，然后从小到大枚举回文半径。

发现两个字符相同就增加以当前字符为对称中心的最大回文串长度，不同就无法继续扩展，换一个对称中心继续，直到枚举完所有对称中心为止。

这个算法时间复杂度 \(O(n^2)\)。

比原做法有所改进，但还不够。

做法四

就是manacher 算法，其实就是上面的做法加了一个优化。

我们记录当前所有回文串能达到的最右边为 \(righ\)，其所在回文串的对称中心为 \(mide\)，以 \(i\) 为对称中心的最大回文半径为 \(dist_i\)，当前枚举到的对称中心为 \(j\)。

当 \(j > righ\) 时，直接使用做法三的方法枚举。

当 \(mide < j \le righ\) 时，给 \(dist_j\) 赋一个初值再枚举。

当 \(j \le mide\) 时，没有这种情况。（原因自己想，我还是懒得证）

赋什么值呢？

由于上面的大小关系，\(j\) 一定在以 \(mide\) 为中心，\(righ\) 为右端的回文串中。

那么 \(j\) 一定有一个关于 \(mide\) 的对称的和它相同的字符，我们设它为 \(k\)。

那么 \(k\) 一定已经被枚举过了，即 \(dist_k\) 也被求出来了。我们可以利用这个信息来赋初值。

比如下面这个串：（这里就没加 '|' 了，下面也一样）

cbabababa

枚举到第 7 个字符 'a' 时，\(j\) 为 7，\(righ\) 为 8，\(mide\) 为 5，\(k\) 则为 3。

那么以 \(mide\) 为对称中心，\(righ\) 为右端的字符串为下面框起来的串：

c[bababab]a

发现 \(disk_k\) 为 1，代表下面框起来的串：

c[bab]ababa

由于回文的性质，与它的对称的串也是个回文串：

cbaba[bab]a

而这个回文串的对称中心就是 \(j\)，所以就可以将 \(dist_k\) 初值设为 \(dist_j\)。

但是这么干下面这个串会有个问题：

ababababc

那么以 \(mide\) 为对称中心，\(righ\) 为右端的字符串还是下面框起来的串：

a[bababab]c

但是 \(disk_k\) 变为 2，代表下面框起来的串：

[ababa]babc

与它的关于 \(mide\) 对称的串却不是回文串：

abab[ababc]

因为这个串的右端已经超出了 \(righ\) 了，然而并不能保证 \(righ\) 右边的字符与它的对称字符相同。

所以初值此时要设为 \(righ-j\)，即下面的串：

ababa[bab]c

综上，最后的 \(dist_j\) 初值应该设为 \(\min(righ-j,dist_k)\)，然后进行扩展，最后还要记得更新 \(righ\) 和 \(mide\)。

然后这个优化就把复杂度骤降为 \(O(n)\)。

证明我还不会，学会了再回来填坑吧/kk

大意就是每次暴力扩展都会把 righ 至少加 1，所以暴力扩展的总次数是 \(O(n)\) 的，而其他部分复杂度不超过 \(O(n)\)，所以总复杂度为 \(O(n)\)。

参考代码

#include
using namespace std;
const int _maxs=11000011;
int slen,maxl,mide,righ,gans[_maxs<<1],rans;
char s[_maxs<<1];
int main(){
    scanf("%s",s+1);
    while('a'<=s[slen+1]&&s[slen+1]<='z')
        slen++;
    s[slen<<1|1]='|';
    for(int i=slen;i;--i){
        s[i<<1]=s[i];
        s[(i<<1)-1]='|';
    }
    slen=slen<<1|1;
    for(int i=1;i<=slen;++i){
        if(i<=righ)
            gans[i]=min(gans[(mide<<1)-i],righ-i);
        while(1<=i-gans[i]-1&&i+gans[i]+1<=slen&&s[i-gans[i]-1]==s[i+gans[i]+1])
            gans[i]++;
        if(righ