求回文字符串最朴素的算法就是我们枚举一个中心点，然后看看该点能够向左向右延伸多远，这样的复杂度是O(n²）

当n很大的时候，我们是无法接受的。我们必须得去优化一下算法.

如何去优化呢？

对于每一个点，我们都是以半径为0开始不断比较。

这似乎显得我们之前已经处理的信息除了记录之外没有别的用途。

能优化是因为我们还没充分地应用之前的信息。

包括求后缀数组等等，我们都是充分应用了之前的信息从而达到了高效。

考虑到这个是回文串，我们可以假设，当前已经找到一个回文字符串，它的中心是p，半径（即回文长度的一半）是r，延伸到最右边的mx=p+i，那么区间$\left[ p-r,p+r\right]$都是对称的

那么我们考察一个在这个区间一个点i，很显然i以前的点我们已经算出来了，因为当前最长的回文串中心p，半径r，根据对称性，2*p-i的点为中心的回文串在区间$\left[ p-r,p+r\right]$内一定会与i点相同，即以i为中心的回文串的半径最少为$\min \left( mx-i,2\ast P-i\right)$(我们已知的信息只有区间$\left[ p-r,p+r\right]$是回文串，不在这个区间的范围内的信息我们并不知晓，因此半径不能超过mx-i），至于超过这个区间的我们只能一一去比较了。如果该回文串延伸到的最右边比之前的mx大，我们就更新p和r就可以了。复杂度为O(n).

 

由于回文串长度有分奇数和偶数情况，为了更好地实现，我们在每个字符旁边加上一个不会出现的特殊符号（如”#“）同时在边缘上再加上另一个符号防止越界，这样下来求得的回文串长度就是奇数了。

1 #include
      
        2 #include
       
         3 #include
        
          4 #define N 100000 5 using namespace std; 6 int n,m,len[N],l,ans; 7 string tmp; 8 char qwq[N]; 9 void insert(){10     l=1;11     qwq[0]='%';12     for (int i=0;i
         
          i) len[i]=min(mx-i,len[2*mx-i]);24         else len[i]=1;25     while (qwq[i+len[i]]==qwq[i-len[i]]) len[i]++;26     if (i+len[i]>mx){    //更新p和mx27         mx=i+len[i];28         p=i;29     }30     ans=max(ans,len[i]);31     }32     return ans-1;   //减去中间那个字符33 }34 int main(){35     cin>>tmp;36     insert();37     printf("%d\n",manacher());38     return 0;39 }