浅谈Manacher

(Manacher)是由一个叫做(Manacher)的人发明的能在(O(n))时间内找出一个字符串长度最长的回文子串的算法。

由于偶回文串形如(abba)这样的不好找对称中心，所以我们在每个字符串之间插入一个'#'，就变成#a#b#b#a#了，这样子就能找到对称中心了。

(Manacher)的核心数组(p_i)：表示以第(i)为为对称中心的回文串半径长度为多少(包含(i))

#	a	#	a	#	b	#	a	#	a	#
1	2	3	2	1	6	1	2	3	2	1

上面一行是字符串，下面一行是(p_i)数组。

以(i)为中心的回文串长度即为(p_i-1)，这个减一可以看做是把最旁边的那个'#'减掉了，然后半径就跟实际上回文串的长度一样了。

所以(manacher)算法的核心就是在(O(n))的时间复杂度内求出(p)数组。

令(mx)为之前已经求出过的(p_i+i-1)的最大值，(id)满足(p_{id}+id-1)等于(mx)的

那么(p_i= ileqslant mx?min(mx-i+1,p[id*2-i]):1)。

这个意思是如果当前位置在(mx)左边，那么当前位置的(p)肯定是(mx-i+1)与我关于(id)对称点的(p)的最小值。因为那个点与我关于(id)对称，所以在([i,mx])这一段内我可以直接继承他的(p)数值，但是当前位置已知的回文串长度不能伸到(mx)后面去，所以跟(mx-i+1)取(min)。

然后在暴力判断能不能继续扩张到(mx)后面去，最后更新(id)和(mx)。

时间复杂度分析：

除了暴力扩张(mx)以外都是(O(1))的，(mx)最多被扩张字符串长度，所以复杂度是(O(n))的。

模板题：https://www.luogu.org/problemnew/show/P3805

时间复杂度：(O(n))

空间复杂度：(O(n))

代码如下：

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int maxn=2.2e7+5;

int n,ans;
int p[maxn];
char s[maxn];

int main() {
    scanf("%s",s+1);
    n=strlen(s+1);
    for(int i=n;i;i--)
        s[i<<1]=s[i],s[(i<<1)-1]='#';
    s[0]='$',s[n<<1|1]='#';n=n<<1|1;
    int id=0,mx=0;
    for(int i=1;i<=n;i++) {
        p[i]=i<=mx?min(mx-i+1,p[id*2-i]):1;
        while(s[i-p[i]]==s[i+p[i]])p[i]++;
        if(i+p[i]-1>mx)id=i,mx=i+p[i]-1;
        ans=max(ans,p[i]);
    }
    printf("%d
",ans-1);
    return 0;
}