Input
Output
Sample Input
abcbabcbabcba abacacbaaaab END
Sample Output
Case 1: 13 Case 2: 6
题意：给一个字符串，找出其中最长回文子串长度
思路：二分枚举其长度，然后枚举每个位置每个位置，利用字符串hash值比较中间位置前后是否一致，需要分奇偶进行二分，因为奇数或者偶数的时候判断前后时候一致的区间不同
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 using namespace std; 6 7 const int maxn = 1e6+5; 8 unsigned long long f1[maxn],f2[maxn],p[maxn]; 9 int even[maxn>>1],odd[maxn>>1]; 10 11 char word[maxn]; 12 int n; 13 14 unsigned long long Find_l(int l,int r) 15 { 16 return f2[n-l+1]-f2[n-r]*p[r-l+1];//逆序hash值 17 } 18 unsigned long long Find_r(int l,int r) 19 { 20 return f1[r]-f1[l-1]*p[r-l+1];//正序hash值 21 } 22 23 int check(int x) 24 { 25 int len = x; 26 x /= 2; 27 if(len & 1) 28 { 29 for(int i=x; i<=n-x-1; i++) 30 if(Find_l(i-x+1,i)==Find_r(i+2,i+x+1)) 31 return len; 32 } 33 else 34 { 35 for(int i=x; i<=n-x; i++) 36 if(Find_l(i-x+1,i)==Find_r(i+1,x+i)) 37 return len; 38 } 39 return 0; 40 } 41 42 int serch(int num[],int l,int r) 43 { 44 int maxx = 1; 45 while(l <= r) 46 { 47 int mid = (l+r) >> 1; 48 int val = check(num[mid]); 49 if(val) 50 { 51 l = mid + 1; 52 maxx = max(val,maxx); 53 } 54 else 55 r = mid - 1; 56 } 57 return maxx; 58 } 59 int main() 60 { 61 int tot1 = 0,tot2 = 0; 62 p[0] = 1; 63 for(int i=1; i<=1000000; i++) 64 { 65 p[i] = p[i-1]*131; 66 if(i&1) 67 odd[++tot1] = i; 68 else 69 even[++tot2] = i; 70 } 71 int cas = 0; 72 while(~scanf("%s",word+1) && word[1] != ‘E‘) 73 { 74 f1[0] = f2[0] = 0; 75 n = strlen(word+1); 76 for(int i=1; i<=n; i++) 77 { 78 f1[i] = f1[i-1]*131 + word[i]-‘a‘+1; 79 f2[i] = f2[i-1]*131 + word[n-i+1]-‘a‘+1; 80 } 81 int ans1 = serch(odd,1,n/2+1); 82 int ans2 = serch(even,1,n/2+1); 83 printf("Case %d: %d\n",++cas,max(ans1,ans2)); 84 } 85 }
Palindrome POJ - 3974 （字符串hash+二分）
原文：https://www.cnblogs.com/iwannabe/p/10676454.html
