题目描述

如果一个字符串正着读和倒着读是一样的，则称它是回文的。

给定一个长度为N的字符串S，求他的最长回文子串的长度是多少。

输入格式

输入将包含最多30个测试用例，每个测试用例占一行，以最多1000000个小写字符的形式给出。

输入以一个以字符串“END”（不包括引号）开头的行表示输入终止。

输出格式

对于输入中的每个测试用例，输出测试用例编号和最大回文子串的长度（参考样例格式）。

每个输出占一行。

样例

输入样例：

abcbabcbabcba
abacacbaaaab
END

输出样例：

Case 1: 13
Case 2: 6

算法

用哈希的 $O(n)$ 算法

既然用了Hash，为什么还要用二分？

直接带入上一个位置的回文串长度，用 Hash 检验是否能达到这个长度，如果可以，再进行延长。

C++ 代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <vector>
#include <algorithm>

#define boost ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define fo(v,a,b) for(int v=(a); v<=(b); v++)
#define fr(v,a,b) for(int v=(a); v>=(b); v--)
#define rng(v,a,b) for(int v=(a); v<(b); v++)

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
template<typename T> T& chmax(T& a, T b) { a = a > b ? a : b; return a;}
template<typename T> T& chmin(T& a, T b) { a = a < b ? a : b; return a;}
const int maxn=1e6+6,P=131;
char s[maxn],a[maxn*2];
ull H1[maxn*2],H2[maxn*2],g[maxn*2];
int main()
{
    int T=0;
    while(cin >> (s+1) && strcmp(s+1, "END")) {
        cout << "Case " << ++T << ": ";
        int len = strlen(s+1), tl=0;
        a[++tl] = '#';
        fo(i,1,len) {
            a[++tl] = s[i]; a[++tl] = '#';
        }
        a[tl+1] = '\0'; len=tl;

        g[0] = 1;
        fo(i,1,len) {
            H1[i] = H1[i-1]*P+a[i]; g[i] = g[i-1]*P;
        }
        fr(i,len,1) H2[i] = H2[i+1]*P+a[i];

        int ans=0,l;
        fo(i,1,len) {
            l=ans;
            if(i+l>=len || i-l<1) break;
            if(H1[i+l]-H1[i-1]*g[l+1] != H2[i-l]-H2[i+1]*g[l+1]) continue;
            while(a[i+l+1] == a[i-l-1] && i+l+1<=len && i-l-1>0) l++;
            chmax(ans,l);
        }
        cout << ans << '\n';
    }
    return 0;
}