A string is said to be a palindrome if it reads the same both forwards and backwards, for example "madam" is a palindrome while "acm" is not.
The students recognized that this is a classical problem but couldn't come up with a solution better than iterating over all substrings and checking whether they are palindrome or not, obviously this algorithm is not efficient at all, after a while Andy raised his hand and said "Okay, I've a better algorithm" and before he starts to explain his idea he stopped for a moment and then said "Well, I've an even better algorithm!".
If you think you know Andy's final solution then prove it! Given a string of at most 1000000 characters find and print the length of the largest palindrome inside this string.
Input
Output
Sample Input
abcbabcbabcba
abacacbaaaab
END
Sample Output
Case 1: 13
Case 2: 6 题意：给一个字符串，找出其中最长回文子串长度
思路：二分枚举其长度，然后枚举每个位置每个位置，利用字符串hash值比较中间位置前后是否一致，需要分奇偶进行二分，因为奇数或者偶数的时候判断前后时候一致的区间不同
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std; const int maxn = 1e6+;
unsigned long long f1[maxn],f2[maxn],p[maxn];
int even[maxn>>],odd[maxn>>]; char word[maxn];
int n; unsigned long long Find_l(int l,int r)
{
return f2[n-l+]-f2[n-r]*p[r-l+];//逆序hash值
}
unsigned long long Find_r(int l,int r)
{
return f1[r]-f1[l-]*p[r-l+];//正序hash值
} int check(int x)
{
int len = x;
x /= ;
if(len & )
{
for(int i=x; i<=n-x-; i++)
if(Find_l(i-x+,i)==Find_r(i+,i+x+))
return len;
}
else
{
for(int i=x; i<=n-x; i++)
if(Find_l(i-x+,i)==Find_r(i+,x+i))
return len;
}
return ;
} int serch(int num[],int l,int r)
{
int maxx = ;
while(l <= r)
{
int mid = (l+r) >> ;
int val = check(num[mid]);
if(val)
{
l = mid + ;
maxx = max(val,maxx);
}
else
r = mid - ;
}
return maxx;
}
int main()
{
int tot1 = ,tot2 = ;
p[] = ;
for(int i=; i<=; i++)
{
p[i] = p[i-]*;
if(i&)
odd[++tot1] = i;
else
even[++tot2] = i;
}
int cas = ;
while(~scanf("%s",word+) && word[] != 'E')
{
f1[] = f2[] = ;
n = strlen(word+);
for(int i=; i<=n; i++)
{
f1[i] = f1[i-]* + word[i]-'a'+;
f2[i] = f2[i-]* + word[n-i+]-'a'+;
}
int ans1 = serch(odd,,n/+);
int ans2 = serch(even,,n/+);
printf("Case %d: %d\n",++cas,max(ans1,ans2));
}
}