题意：求一个字符串的最长回文子串
题解：是一个Manacher模板题，为了统一奇偶，先预处理在字符间添加间隔，使字符串长度变为偶数，例如"abc"添加分隔符后变成"$#a#b#c#"，剩下的就很简单了，这个题也可以用哈希做。就时间复杂度来看Manacher明显比哈希快。
Manacher代码
1 #include<stdio.h> 2 #include<algorithm> 3 #include<string.h> 4 #include<string> 5 using namespace std; 6 7 int p[2000020];//p数组需要开至少字符串两倍的空间 8 char s[1010100]; 9 10 int Manacher(char str[]) 11 { 12 memset(p,0,sizeof(p)); 13 string s="$#"; 14 int len=strlen(str); 15 for(int i=0;i<len;i++){ 16 s+=str[i]; 17 s+='#'; 18 } 19 int mx=0,id=0,reslen=0,rescenter=0; 20 len=s.length(); 21 for(int i=1;i<=len;i++) 22 { 23 p[i]=mx>i?min(p[2*id-i],mx-i):1;// 24 while(s[i+p[i]]==s[i-p[i]])p[i]++; 25 if(mx<i+p[i]) 26 { 27 mx=i+p[i]; 28 id=i; 29 } 30 if(reslen<p[i]) 31 { 32 reslen=p[i]; 33 rescenter=i; 34 } 35 } 36 return reslen-1; 37 } 38 39 40 int main() 41 { 42 int t=1; 43 while(~scanf("%s",s)){ 44 if(strcmp(s,"END")==0) break; 45 printf("Case %d: %d ",t++,Manacher(s)); 46 } 47 return 0; 48 }
哈希代码
1 #include<stdio.h> 2 #include<algorithm> 3 #include<string.h> 4 #include<math.h> 5 #include<iostream> 6 using namespace std; 7 8 const int maxn = 2e6+20; 9 const int base = 131; //不易冲突 10 typedef unsigned long long ULL; 11 ULL f[maxn], f2[maxn], t[maxn]; 12 13 char s[maxn]; 14 ULL solve(ULL h[],int l, int r) 15 { 16 return h[r] - h[l-1] * t[r-l+1]; 17 } 18 19 int main() 20 { 21 int T = 1; 22 while(scanf("%s", s+1) != EOF) { 23 int len = strlen(s+1); 24 if(!strcmp(s+1, "END")) 25 break; 26 for(int i = 2*len; i > 0; i-=2) { 27 s[i] = s[i/2]; 28 s[i-1] = 'z'+1; 29 } 30 len *= 2; 31 f[0] = f2[0] = 0; 32 t[0] = 1; 33 for(int i = 1, j = len; i <= len; i++, j--) { 34 f[i] = f[i-1]*base + (s[i] - 'a' + 1); 35 f2[i] = f2[i-1]*base + (s[j] - 'a' + 1); 36 t[i] = t[i-1] * base; 37 } 38 int l, r; 39 int ans = 0; 40 int mid; 41 for(int i = 1; i <= len; i++) { 42 l = 0, r = min(i-1, len-i); 43 while(l < r) { 44 mid = (l+r+1)>>1; 45 if(solve(f,i-mid,i-1) != solve(f2,len-(i+mid)+1,len-(i+1)+1)) 46 r = mid-1; 47 else l = mid; 48 } 49 if(s[i-l] <= 'z') 50 ans = max(ans, l+1); 51 else 52 ans = max(ans, l); 53 } 54 printf("Case %d: %d ", T++, ans); 55 } 56 return 0; 57 }