题目就是求字符串中最长回文串的长度。
一道马拉车板子题，就附带讲讲我对马拉车算法的理解。
马拉车算法时间复杂度是O(n)的，它巧妙地把将长度为奇数的回文串和长度为偶数的回文串一起考虑。它在字符与字符之间加了一个没有出现过的字符（一般都是'#'）。
主要有一个len[i]数组求 以p[i]字符为回文串中心时，最大回文串中最右字符到p[i]有几个字符（包括s[i]）。
比如样例 daabaac
改了之后 # d # a # a # b # a # a # c #
len[i] 1 2 1 2 3 2 1 6 1 2 3 2 1 2 1
答案就是最大的len[i]-1,因为总长度是2*len[i]-1,而'#'占len[i]个所以答案就是len[i]-1.很显然这里答案是5（aabaa）
怎么求len[i]呢？
首先从左往右依次计算len[i]，当计算len[i]时，len[j](0<=j<i)已经计算完毕。设mx为之前计算中最长回文子串的右端点，并且设取得这个最长回文子串的中心位置为po，分两种情况：
1.i<mx(最核心的部分) 即该计算字符还在之前计算最长回文子串中
len[i]=min(mx-i,len[2*po-i]）//i和2*po-i 是关于po对称的，注意i是大于po的，所以2*po-1是在po的左边，是已知的。
while(p[i-len[i]]==p[i+len[i]])
len[i]++;
为什么取mx-i和len[2*po-i]的最小？
情况一：len[2*po-i]<mx-i
举例：
1 2 3 4 5 6 7 8 9 10 11 12
a a a a a b a a a a a c（这里没有加'#',是本人太懒了，但效果是一样的）
当遍历到i，即红色的a时， 此时最长回文子串是aaaabaaaa,mx=11,po=6。
此时2*po-i为蓝色的a 以其为中心的回文串一定是在(2*po-mx)~po~mx（此时最大回文串中，1~11）
因为len[4]=2<mx-i=3时，,因为对称关系，345回文是，789一定回文，len[i]>=len[2*po-1],
大于是因为可能以i为中心回文子串时，最右端可能超过了mx.
情况二：len[2*po-1]>=mx-i
举例：
1 2 3 4 5 6 7 8 9 10 11
a a a a a b a a a a c
当遍历到红色的a时， 此时最长回文子串是aaaabaaaa,mx=10,po=6。
len[9]<len[3]但是len[9]一定是>=mx-i的，因为len[3]>=mx-i，所以234一定是回文串，即8910一定是回文串。
总而言之，由于,回文串中对称关系，len[i]>=min(mx-i,len[2*po-i])
2.i>=mx
直接匹配就可以了
len[i]=1;
while(p[i-len[i]]==p[i+len[i]])
len[i]++;
代码:
#include<iostream> #include<algorithm> #include<cstring> using namespace std; const int maxn=200050; char s[maxn],p[maxn];//s为原串,p为改变之后的串 int len[maxn]; void init()//初始p串 { p[0]='@'; int l=strlen(s); for(int i=1;i<=2*l;i+=2) { p[i]='#'; p[i+1]=s[i/2]; } p[l*2+1]='#'; p[l*2+2]='!'; } int manacher() { int mx=0,po=0,ans=0; int l=strlen(p); for(int i=1;i<=l;i++) { if(mx>i) len[i]=min(mx-i,len[2*po-i]);//核心 else len[i]=1; while(p[i-len[i]]==p[i+len[i]]) len[i]++; if(len[i]+i>mx)//替换最大回文子串 { mx=len[i]+i; po=i; } ans=max(ans,len[i]); } return ans-1; } int main() { cin>>s; init(); cout<<manacher()<<endl; }