[cpp] /**************************************************** 算法引入： 回文串指的是一個正著讀和反著讀都一樣的字符串; 要在一個字符串中求出它的長度最長的回文子串; 算法思想： Manacher算法可以在O(n)的線性時間復雜度的情況下; 求出以每個字符為中心的最長回文子串有多長; 該算法把奇數的回文串和偶數的回文串統一起來考慮; 大大的減少了奇數串和偶數串分開處理的麻煩; 該算法充分利用了字符匹配的特殊性，避免了大量不必要的重復匹配; 然後用一個輔助數組P記錄以每個字符為中心的最長回文串的信息; P[i]記錄的是以字符s[i]為中心的最長回文串; 當以s[i]為第一個字符，這個最長回文串向右延伸了P[i]個字符; 由p數組的性質，新串中以s[i]為中間字符的回文串的長度為p[i]-1; 以#為中間字符的就是長度為偶數的,以非#號為中間字符的就是長度為奇數的; 只要在O(n)時間復雜度內求出P數組; 最長回文子串就可以只需掃描一遍p數組就可以得到結果了; 算法過程： 先在每兩個相鄰字符中間插入一個分隔符; 當然這個分隔符要在原串中沒有出現過，一般可以用‘#’分隔; 這樣就非常巧妙的將奇數長度回文串與偶數長度回文串統一起來考慮了; 即此時回文串長度全為奇數了,為了防止字符比較的時候指針小於0; 在加了‘#’的字符串之前還加了字符‘$’,即新串下標是從1開始的; 由於這個算法是線性從前往後掃描的; 那麼准備求P[i]的時候; i以前的P[j]是已經得到了的; 用變量k表示在i之前的回文串中，延伸至最右端的位置; 同時用變量pos記下取得這個最優的k時的位置; 算法測試： hdu3068 *****************************************************/ #include<iostream> #include<cstdio> #include<cmath> #include<cstring> #include<cstdlib> #include<algorithm> using namespace std; const int N=100010; char s[N*2],str[N]; int p[N*2]; int n; int min(int x,int y) { return x<y?x:y; } void init() { n=strlen(str); s[0]='$'; s[1]='#'; for(int i=0; i<n; i++) { s[i*2+2]=str[i]; s[i*2+3]='#'; } n=n*2+2; s[n]='\0'; } void Manacher() { int k=0;//k表示在i之前的回文串中，延伸至最右端的位置 int pos;//pos表示取得這個最優的k時的位置 for(int i=1; i<n; i++) { if(k>i)//當前面比較的最遠長度k>i的時候，P[i]有一個最小值 p[i]=min(p[2*pos-i],k-i); else p[i]=1; while(s[i+p[i]]==s[i-p[i]]) { p[i]++; } if(p[i]+i>k) { k=p[i]+i; pos=i; } } } int main() { //freopen("C:\\Users\\Administrator\\Desktop\\kd.txt","r",stdin); while(~scanf("%s",str)) { init(); Manacher(); int res=0; for(int i=1; i<n; i++) { if(res<p[i]) res=p[i]; } printf("%d\n",res-1); } return 0; }
