求最长回文串

给出一个只由小写英文字符a,b,c...y,z组成的字符串S,求S中最长回文串的长度. 回文就是正反读都是一样的字符串,如aba, abba等 Input 输入有多组case,不超过120组,每组输入为一行小写英文字符a,b,c...y,z组成的字符串S 两组case之间由空行隔开(该空行不用处理) 字符串长度len <= 110000 Output 每一行一个整数x,对应一组case,表示该组case的字符串中所包含的最长回文长度. Sample Input aaaa abab Sample Output 4

3

---------------------我是逗比的分界线-------------------------------------------------------------------------

思路分析：

该题采用Manacher方法求回文串，达到接近O(n)的时间复杂度。

总结回顾：

写完后用例能过，但老是时间超时，先是把所有的cin、cout改成c的输入输出，但还是超时。

最后发现在Manacher函数中每次都给p数组分配内存和初始化，导致时间超时。

#include <iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> /* run this program usin g the console pauser or add your own getch, system("pause") or input loop */ using namespace std; const int MAX=220002; char a[MAX],b[MAX]; int p[MAX]; //每次分配内存就会造成时间超时； /* 先对数组进行变换 再计算回文串的长度 */ int manacher(char *b,int len) { p[0]=1; int mx=0,id=0; for(int i=1;i<=len;i++) { if(mx>i) { p[i]=min(p[2*id-i],mx-i); } else { p[i]=1; } while(i+p[i]<=len&&b[i-p[i]]==b[i+p[i]])p[i]++; if(p[i]+i>mx) { mx=p[i]+i; id=i; } } int ma=0; for(int i=1;i<=len;i++) { if(p[i]>ma) ma=p[i]; } return ma-1; } int main(int argc, char** argv) { while(scanf("%s",a)!=EOF) { int size=strlen(a); b[0]='$'; b[1]='#'; int j=2; for(int i=0;i<size;i++) { b[j++]=a[i]; b[j++]='#'; } b[j]='^'; int result=manacher(b,j); printf("%d\n",result); } return 0; }