题目链接

解题思路

??马拉车当然是求最长回文既简单又快速的方法，不过这里因为要联系hash就没用马拉车了。设回文串的中心为a,b(奇回文a=b)先正着hash一遍，再倒着hash一遍，就能得到[a+len,a]和颠倒后的[b,b+len]两个子串哈希值，对比它们的哈希值就能判断两个子串是否相等，至于len的大小，用二分来判定就行了。

代码

const int maxn = 1e6+10;char s[maxn];int n, kase = 1;unsigned long long f[maxn], rf[maxn], p[maxn] = {1};int solve(int a, int b) { int l = 0, r = min(a-1,n-b); while(l<r) { int mid = (l+r+1)>>1; if (f[a]-f[a-mid-1]*p[mid+1]==rf[b]-rf[b+mid+1]*p[mid+1]) l = mid; else r = mid-1; } return s[a]==s[b] ? l:-1;}int main() { while(~scanf("%s",s+1) && s[1]!=‘E‘) { n = strlen(s+1); for (int i = 1; i<=n; ++i) { f[i] = f[i-1]*131+s[i]-‘a‘+1; p[i] = p[i-1]*131; } rf[n+1] = 0; for (int i = n; i>=1; --i) rf[i] = rf[i+1]*131+s[i]-‘a‘+1; int ans = 1; for (int i = 2; i<=n; ++i) { ans = max(ans, solve(i,i)*2+1); ans = max(ans, solve(i-1,i)*2+2); } printf("Case %d: %d\n", kase++, ans); } return 0;}