上天折断了你飞翔的羽翼，你也要给自己一双翅膀！

这个算法主要处理回文串。

举个栗子：求字符串中最长回文串的长度（暴力pass掉的那种）

abacbaa

在其中插入一个符号（不能出现字符串中的，大家都懂的）#

变成了#a#b#a#c#b#a#a#(#是从1开始的，前面新构造的数组0位置要存另一种符号)

然后，构造一个p数组，p[i]表示一i为中间点的最长的回文串最右边字符到中间字符的长度，id表示当前字符

，p数组有一个性质，那就是p[i]-1就是该回文子串在原字符串S中的长度。

证明：首先在转换得到的字符串T中，所有的回文字串的长度都为奇数，那么对于以T[i]为中心的最长回文字串，其长度就为2*p[i]-1,经过观察可知，T中所有的回文子串，其中分隔符的数量一定比其他字符的数量多1，也就是有p[i]个分隔符，剩下p[i]-1个字符来自原字符串，所以该回文串在原字符串中的长度就为p[i]-1。

下面上代码（我把构造新数组的代码也打出来了呦）

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
///修改后的字符串长度是原字符串长度的两倍多一
char s[100005],T[100005];
///辅助数组Len[i]表示以字符T[i]为中心的
///长回文字串的最右字符到T[i]的长度
int p[100005];
///初始化辅助数组
void init()
{
    int len=strlen(s);
    T[0]='$';
    T[1]='#';
    for(int i=0; i<len; i++)
    {
        T[i*2+2]=s[i];
        T[i*2+3]='#';
    }
    T[2*len+2]='\0';///不要忘记'\0'
}
void manacher()
{
    int len=strlen(T);
    int id=-1;///id为右边界最大的回文串的中心
    int mx=0;///mx为以T[id]为中心的最长回文最右边界
    for(int i=1; i<len; i++)
    {
        if(i<mx) 
            p[i]=min(p[id*2-i],mx-i);
        else 
            p[i]=1;
        while(T[i+p[i]]==T[i-p[i]])///判断该回文串是否还可以扩充
            p[i]++;
        ///每走一步都要更新mx，因为我们希望mx尽可能的大，
        ///这样才有机会执行if(i<mx),从而降低算法的时间复杂度
        if(mx<i+p[i])
        {
            mx=i+p[i];
            id=i;
        }
    }
}
int main()
{
    scanf("%s",s);
    init();
    manacher();
    int len=strlen(T);
    int ans=-1;
    for(int i=1; i<len; i++)
        ans=max(ans,p[i]-1);
    cout<<ans<<endl;
    return 0;
}

大家一定要按代码手动模拟一遍，特别要理解if和else这两行。mx在i的右边，最长也就是他自己呗。

最后附上一张盗来的图让大家更直观的感受到位置查找回文的过程