转载请注明出处： http://www.cnblogs.com/fraud/ ——by fraud
求最长回文子串。
http://acm.timus.ru/problem.aspx?space=1&num=1297
Manacher模板题，复杂度O（n），做这题纯属是为了验一下自己写的模板是否正确。
当然这题也可以用后缀数组来搞
1 #include <iostream> 2 #include <sstream> 3 #include <ios> 4 #include <iomanip> 5 #include <functional> 6 #include <algorithm> 7 #include <vector> 8 #include <string> 9 #include <list> 10 #include <queue> 11 #include <deque> 12 #include <stack> 13 #include <set> 14 #include <map> 15 #include <cstdio> 16 #include <cstdlib> 17 #include <cmath> 18 #include <cstring> 19 #include <climits> 20 #include <cctype> 21 using namespace std; 22 #define XINF INT_MAX 23 #define INF 0x3FFFFFFF 24 #define MP(X,Y) make_pair(X,Y) 25 #define PB(X) push_back(X) 26 #define REP(X,N) for(int X=0;X<N;X++) 27 #define REP2(X,L,R) for(int X=L;X<=R;X++) 28 #define DEP(X,R,L) for(int X=R;X>=L;X--) 29 #define CLR(A,X) memset(A,X,sizeof(A)) 30 #define IT iterator 31 typedef long long ll; 32 typedef pair<int,int> PII; 33 typedef vector<PII> VII; 34 typedef vector<int> VI; 35 #define MAXN 100010 36 char str[MAXN],s[MAXN]; 37 int p[MAXN]; 38 int n; 39 void Manacher(){ 40 n=strlen(s); 41 str[0]='$'; 42 str[1]='#'; 43 for(int i=0;i<n;i++)str[2*i+2]=s[i],str[2*i+3]='#'; 44 n=n*2+2; 45 str[n]=0; 46 int mx=0,id; 47 for(int i=1;i<n;i++){ 48 if(mx>i)p[i]=min(p[2*id-i],mx-i); 49 else p[i]=1; 50 for(;str[i+p[i]]==str[i-p[i]];p[i]++); 51 if(p[i]+i>mx)mx=p[i]+i,id=i; 52 } 53 } 54 55 int main() 56 { 57 ios::sync_with_stdio(false); 58 while(scanf("%s",s)!=EOF){ 59 Manacher(); 60 int ans=1; 61 int id; 62 int maxx=1; 63 for(int i=0;i<n;i++){ 64 if(p[i]>maxx)id=i,maxx=p[i]; 65 } 66 //cout<<maxx<<endl; 67 p[id]--; 68 for(int i=id-p[id];i<=id+p[id];i++){ 69 if(str[i]=='#')continue; 70 printf("%c",str[i]); 71 } 72 puts(""); 73 } 74 return 0; 75 }