马拉车算法用于求解最长回文子串的长度。
51nod题目链接
坑点：
1.因为需要在每个字符之间插入#，所以记录数组和新的字符数组的长度应该是2*n,否则会runtime error
2.在新的字符串的开头必须加入一个防止访问越界的标记@
为什么呢，因为如果不做这个处理会发现在遍历第一个while循环的时候，发生数组越界，所以这也是个坑点
#include<cstring>
#include<iostream>
using namespace std;
int main(){char x[100005],y[200005];int p[200005],len;memset(p,0,sizeof(p));cin>>x;len = strlen(x);y[0] = '@';for(int i = 0;i<len;i++){y[2*i+1] = '#';y[2*i+2] = x[i];}y[2*len+1] = '#';int ans = 0,mid = 0,Rmax = 0;for(int i = 1;i<=2*len+1;i++){p[i] = i<Rmax?min(Rmax - i,p[2*mid - i]):1;while(y[i+p[i]] == y[i-p[i]])p[i] ++;if(i+p[i] > Rmax){Rmax = i+p[i];mid = i;}ans = max(ans,p[i] - 1);}cout<<ans;
}
算法解析：
如果暴力求解，则思路是遍历每个字符，把它当做对称中心，然后向两侧遍历，O（n*n）的复杂度
但是分析一下对称串的性质，可以从中发现规律，从而减小复杂度。
具体思路：
1.在每个字符中间插入其他不会出现的特殊字符#（可以任意选择）
目的是 ：不管你找到的字符串是奇数还是偶数个，在这样的预处理后，结果一定是奇数个字符 即 #.#.------#-------.#.#的形式
减少讨论的次数
2.核心代码：p[i] = i<Rmax?min( Rmax-i , p[2*mid-i])
每次遍历新的串的第i个字符的时候，我们维护俩个变量，即当前求得的回文串的最右端的下标号和这个串的对称中心下标
如果新的i在小于Rmax的范围内，用对称性原理，找到i关于中心mid 的对称点j 那么在[i,Rmax]的范围内的回文对称性可以由p[j]得到，从而减小的向两侧比较的次数。
但是大于Rmax的范围任然需要暴力比较，但是这样的复杂度大大减小。
最后分析下结果为什么是找到ans = max(ans,p[i]-1)
如果看不懂解释，可以自己按照假设的思路自己推导
---假设i处字符是# ，那么此处的回文串是 #x#x # x#x#的形式,即单侧的个数是偶数个，设单侧个数为t，而实际x符号的个数是 t/2 *2 == t个，
而p[i] = 1 + t 所以这个情况下 回文串的长度是t 即 p[i] -1
---假设i处的字符是x，那么此处的回文串形式是 #x# x #x# 即单侧的个数是奇数个，设单侧的个数为2*t' +1 即#x#，而实际x的个数是t'个，所以这个串的x的个数是 2*t'（俩侧） + 1(中心) ,而p[i] = （2*t' +1）+1所以 串的实际长度是p[i]-1
综上所述，串的长度就是p[i] -1 ,找到最大的 那个值即可
ps：p[i]记录的是某回文串 从中心到某一侧的字符个数，即只算上 （半径+1）。