題意：給一個字元串，求最長回文子串的長度。
思路：
（1）暴力窮舉。O(n^3) -----絕對不行。
窮舉所有可能的出現子串O(n^2)，再判斷是否回文O(n)。就是O(n*n*n)了。
（2）記錄位置。O(n^3) -----絕對不行。
先掃一遍，記錄每個字元在上一次出現的位置pos。每次考慮第i個字元，如果回文子串包括 i 的話，那麼肯定在i的前面有一個跟第i個字元是一樣的，利用之前記錄的位置pos[i]可以找到與第i個相同的字元，如果i-pos[i]比之前發現的最長的子串max還短，那麼不用比較了。如果更前面還有和第i個字元一樣的，那麼可以找到第pos[pos[i]]個，一定要找到區間比max還大的，才有比較的意義，除非前面已經沒有相同字元的了。那麼略過第i個，直奔下一個。記錄位置需要O(n)，考慮每個字元需要O(n)，對其前面出現過的每個字元考慮O(n)，一旦考慮就需要比較是否回文O(n)，總的來說，後面3個是乘的關系O(n^3)。
1 #include <iostream>
2 #include <cstring>
3 #include <vector>
4 #include <stdio.h>
5
6 using namespace std;
7 const int N=1000010;
8
9 char str[N];
10 char has[256];
11 char pos[N];
12
13
14 bool isP(int j,int i)
15 {
16 while( j!=i && j!=--i)
17 {
18 if( str[j]!=str[i] )
19 return false;
20 j++;
21 }
22 return true;
23 }
24
25 int fin_ex(int max, int i)
26 {
27 int j=pos[i];
28 while( i-j<=max && j>-1 ) //找到一個區間範圍大于max的，開始算
29 j=pos[j];
30 return j;
31 }
32
33 int cal(int len)
34 {
35 int max=1, j;
36 for(int i=0; i<len; i++)
37 {
38 j=fin_ex(max, i); //找相同的，且大于max的
39 while( j!=-1 && i-j>max ) //有相同
40 {
41 if(isP(j,i+1)==true)
42 max=i-j+1;
43 else
44 j=fin_ex(max, j); //不是回文，繼續找
45 }
46 }
47 return max;
48 }
49
50
51 int main()
52 {
53 //freopen("input.txt", "r", stdin);
54 int t;
55 cin>>t;
56 getchar();
57 while(t--)
58 {
59 gets(str);
60 int len=strlen(str);
61 for(int i=0; i<256; i++) has[i]=-1; //初始化
62 for(int i=0; i<len; i++) //記錄上一次出現的位置
63 {
64 pos[i]=has[str[i]];
65 has[str[i]]=i;
66 }
67
68 cout<<cal(len)<<endl;
69 }
70 return 0;
71 } TLE代碼
（3）動态規劃。時間O(n^2)，空間O(n^2)----這空間已經不行了。
不考慮了，這空間接受不了。
（4）中心擴充。時間O（n^2），空間O（0）。-----這時間已經不行了。
掃一遍每個字元需要O（n），對每個字元進行回文判斷需要O（n）。總的就O（n^2）。
1 #include <iostream>
2 #include <cstring>
3 #include <vector>
4 #include <stdio.h>
5
6 using namespace std;
7 const int N=1000010;
8 int len;
9 char str[N];
10
11 int isP(int i) //以i為中點的最長回文串的長度
12 {
13 int max1=1;
14 //奇數
15 int tmp=max(i,len-i-1);
16
17 for(int j=1; j<=tmp; j++)
18 {
19 if( str[i-j]==str[i+j] )
20 max1+=2;
21 else
22 break;
23 }
24
25 //偶數
26 int max2=0;
27 tmp =max(i+1, len-i-1);
28 for(int j=0; j<tmp; j++)
29 {
30 if( str[i-j]==str[i+j+1] )
31 max2+=2;
32 else
33 break;
34 }
35 return max1>max2? max1:max2;
36 }
37
38 int cal()
39 {
40 int max=1, tmp;
41 for(int i=1; i<len-1; i++) //考慮以i為中心的回文串
42 {
43 if( (tmp=isP(i))>max )
44 max=tmp;
45 }
46 return max;
47
48 }
49
50 int main()
51 {
52 //freopen("input.txt", "r", stdin);
53 int t;
54 cin>>t;
55 while(t--)
56 {
57 scanf("%s",str);
58 len=strlen(str);
59 if(len==1){cout<<"1"<<endl;continue;}
60 cout<<cal()<<endl;
61 }
62 return 0;
63 } （5）Manacher算法。時間O（n），空間O（n）。------完全OK！
主要目的就是要減少計算量，在”中心擴充“法的基礎上，節省更多的計算量。下面介紹這種處理方法。
步驟：
1）首先要插入一些奇怪的字元。作用是，使得每種可能出現的子串的長度變成永遠是奇數。如 abba 變成 #a#b#b#a#。假設串長為n，那麼其實是加入了n+1個#号，使得串長總是2*n+1，這樣就必定是奇數了。而且在用”中心擴充“法時仍然是奇數，考慮奇數子串#b#，偶數子串b#b，如果中間是#号，那麼計算的就是偶數的子串了。置s[0]=‘￥’，随便一個特殊的字元，可以省去計算時的判斷的左邊界，比對到這個￥特殊符号，肯定沒有任何一個是跟他比對的，最長比對過程自動就被終止了。而右邊界有'\0'，自然也沒有任何符号會跟他比對。
2）接着需要記錄下每個字元的關于最長子串的一些“資訊”，不是長度，而是一個可以計算出長度的數字，其實是（純長度+1），為什麼要這麼做？這其實是個邊界。即下面提到的mx，在i到mx之間的字元都可以節省一些計算量。
（mx的對稱點，id）和（id，mx）是對稱的，即是回文的。能使得mx越靠右的字元位置就作為id，是以得及時憑借mx大小來更新id和mx。在（id，mx）中任意一個位置i都會和id左邊對稱的位置j有着一樣的字元，那麼以 i為中心的最小回文就跟以 j為中心的最大回文有關了，這也是減少計算量的突破口。假設用P[i]記錄以位置i為中心的最長回文串的長度資訊的話，有下面兩種情況：
（1）以j為中心的最長回文串是（mx的對稱點，id）裡面的某一部分，則j-P[j]不會超過左邊”mx的對稱點“ 。那麼這在P[id]管轄的範圍内，有左右對稱的原理，是以P[i]至少為P[j]吧，但是可能會更大，因為左邊的是比較過的才求出P[j]，這P[i]還沒比較過，是以長度可以從P[j]開始比對了。這樣就節省了這P[j]次比較了。
（2）P[j]超過了左邊”mx的對稱點“ 。超過了id的管轄範圍了，多出的部分保證不了左右對稱的原理了，但是在id管轄範圍内的肯定是符合對稱原理的，那麼至少也可以減少一些計算量呐，減多少呢？就是”id管轄範圍内“那個P[j]的長度了，做一些計算就可以得到這個長度是多少，但是肯定是小于P[j]的。
注：那如果i逐漸掃到mx之外了怎麼辦，i肯定找不到再關于id對稱的j了。那就老老實實比較吧，繼續用中心擴充。
1 #include <iostream>
2 #include <cstring>
3 #include <vector>
4 #include <stdio.h>
5 using namespace std;
6 const int N=1000010;
7 int len; //原串長
8 char str[N]; //接收原來的串
9 char s[N*2]; //做了插入處理的結果串
10 int P[N*2]; //儲存關于長度的資訊（回文長度的一半再加1）
11 int cal()
12 {
13 int id=1, mx=1, max1=1;
14 P[0]=1;
15 P[1]=1;
16 for(int i=2; s[i]!='\0'; i++) //考慮以i為中心的回文串
17 {
18 P[i] =i>mx? 1: min( P[2*id-i],mx-i);
19 while(s[i+P[i]]==s[i-P[i]]) //在這比對
20 P[i]++;
21 if(i+P[i]>mx) //更新id和mx的位置
22 {
23 id=i;
24 mx=i+P[i];
25 }
26 if(P[i]-1>max1) //更新最大值
27 max1=P[i]-1;
28 }
29 return max1;
30 }
31
32 int main()
33 {
34 freopen("input.txt", "r", stdin);
35 int t;
36 cin>>t;
37 while(t--)
38 {
39 scanf("%s",str);
40 len=strlen(str);
41 memset(s,0,sizeof(s));
42 memset(P,0,sizeof(P));
43
44 //插入符号#
45 s[0]='$';
46 s[1]='#';
47 int i=0, j=2;
48 for(; i<len; i++)
49 {
50 s[j++]=str[i];
51 s[j++]='#';
52 }
53 cout<<cal()<<endl;
54 }
55 return 0;
56 } AC代碼
用String實作了一發：
1 #include <bits/stdc++.h>
2 #define INF 0x7f7f7f7f
3 #define pii pair<int,int>
4 #define LL unsigned long long
5 using namespace std;
6 const int N=20100;
7
8 int Manacher(string &str, int len)
9 {
10 //插上輔助字元#
11 string tmp(len*2+2,'#');
12 tmp[0]='$';
13 for(int i=0; i<str.size(); i++) tmp[i*2+2]=str[i];
14
15 int ans=1;
16 int mx=1, id=1;
17 vector<int> P(2*len+2,0);
18
19 for(int i=2; i<tmp.size(); i++)
20 {
21 P[i]=( i>=mx? 1: min( P[2*id-i], mx-i ));
22 while( tmp[i-P[i]]==tmp[i+P[i]] ) P[i]++; //比對了就繼續擴大P[i]
23
24 if(mx<=i+P[i])//重要：更新位置
25 {
26 mx=i+P[i];
27 id=i;
28 }
29 ans=max(ans, P[i]-1); //這就是長度了，不信動手畫。
30 }
31 return ans;
32 }
33
34 int main()
35 {
36 freopen("input.txt", "r", stdin);
37 int t;
38 string str;
39 cin>>t;
40 while(t--)
41 {
42 cin>>str;
43 cout<<Manacher(str, str.size())<<endl;;
44 }
45 return 0;
46 }