回文串
杭电3068 最长回文串(manachar)：
题目：
给出一个只由小写英文字符a,b,c...y,z组成的字符串S,求S中最长回文串的长度.
回文就是正反读都是一样的字符串,如aba, abba等
#include<iostream>
#include<string.h>
using namespace std;
const int maxn = 110000 + 10;
char a[maxn];
int p[maxn * 2];
int Min(int a, int b){
return a > b ? b : a;
}
int main(){
int i, n, id, maxl, maxid;
while(scanf("%s",a) != EOF){
char b[maxn * 2];
maxl = 0;
maxid = 0;
id = 0;
int j = 2;
for(i=0; a[i] != '\0'; i++){ //插入#号，解决奇偶性问题
b[j++] = a[i];
b[j++] = '#';
}
b[0] = '@'; //防止越界
b[1] = '#';
n = strlen(a) * 2 + 1;
for(i=1; i<n; i++){
if(maxid > i){ //处理重复，核心（优化是时间），为什么选最少的原因看上图
p[i] = Min(p[2 * id -i],maxid - i);
}
else{
p[i] = 1;
}
while(b[i + p[i]] == b[i - p[i]]){ //向两边扩充，找到最大回文
p[i]++;
}
if(p[i] + i > maxid){
maxid = p[i] + i;
id = i;
}
if(p[i] > maxl){
maxl = p[i];
}
}
printf("%d\n",maxl - 1);
}
return 0;
}