一、算法简介

manacher算法是一款用于匹配回文串的线性算法。

其实现原理为利用回文串的对称性进行预处理回文串长度后暴力扩展。

二、原理实现

（以下解释均基于长度为奇数的回文串进行）

设右端点最靠右的回文串中回文中心为 mid，其右端点为 r，此时处理到的位置为 i，其回文串半径为 pi​

右端点最靠右是保证manacher算法 O(n) 复杂度的关键。

若有 mid≤i≤r，则有 i 以 mid 为中心的对称点 i′=mid∗2−i。

由于回文串的对称性，在处理 i 时可以先将 pi​ 扩展到 pi′​ 的位置，但如果此时扩展到了 r 右侧，则无法保证其回文性质，因此有：

pi​=min(pi′​,r−i+1)=min(p(2∗mid−1)​,r−i+1)

接下来就可以直接暴力扩展了，在暴力扩展过程中如果出现了 pi​+i>r 的情况，则更新右端点最右的回文串中心 mid 与半径 r。

三、具体实现

1.预处理

在进行匹配之前，需要先将奇数长度与偶数长度回文串统一预处理为同种情况以便于处理。

在原字符串的每个数之间插入一个原字符串中不会出现的字符，此时偶数情况的回文串的回文中心相当于此字符。

同时在开头加入一个与之前字符都不相同的终止符，防止匹配越界。

2.匹配回文串

对于位置 i，如果其处于已处理的右端点最靠右回文串范围内，则可以直接更新，否则将其半径定为 1，再在接下来扩展并更新回文串。

四、复杂度证明

由于每次更新回文串只会向右侧更新，因此每个点只会扫到一遍，显然有其线性复杂度 O(n)。

五、用处

匹配以每个点为中心的回文串长度。

六、程序

以P3805 【模板】manacher算法为例:

using namespace std;
const int MAXN=22000005;
int a=0,b,c;
int p[MAXN];
string cmp;
char rep[MAXN];
inline int read()
{
    char x=getchar();int t=0;
    while(!isdigit(x))x=getchar();
    while(isdigit(x))t=(t<<3)+(t<<1)+(x^48),x=getchar();
    return t;
}
int main()
{
    cin>>cmp;
    rep[0]='$',rep[++a]='#';
    for(int i=1;i<=cmp.size();++i)
        rep[++a]=cmp[i-1],rep[++a]='#';
//    cerr<<"!";
    int mid=0,len=0;
    for(int i=2;i<=a;++i)
    {
        if(i<=len)p[i]=min(p[(mid<<1)-i],len-i+1);
        else p[i]=1;
        while(rep[p[i]+i]==rep[i-p[i]]&&i-p[i]>0)
        {
//            cerr<<p[i]+i;
            if(p[i]+i>len)len=p[i]+i,mid=i;
            p[i]++;
        }
    }
    int ans=0;
    for(int i=1;i<=a;++i)ans=max(ans,p[i]);
    printf("%d",ans-1);
    return 0;
}