题目描述

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

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

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

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

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

每个输出占一行。

样例

输入样例：
abcbabcbabcba
abacacbaaaab
END
输出样例：
Case 1: 13
Case 2: 6

算法1

(字符串哈希) $O(n^logn)$

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1e6 + 10 , P = 131;

int n;
char s[N];
int p[N];
int f[N] , g[N];

void h(){

    p[0] = 1;
    for(int i = 1 , j = n ; i <= n ;i++ ,j--)
    {
        f[i] = f[i - 1] * P + (s[i] - 'a') + 1;
        g[i] = g[i - 1] * P + (s[j] - 'a') + 1;
        p[i] = p[i - 1] * P;
    }
}
int main(){

    int t = 0;
    while(scanf("%s" , s + 1) , strcmp(s + 1 , "END"))
    {
        n = strlen(s + 1);
        h();
        int res = 0;
        for(int i = 1 ; i <= n;i++)
        {
            int l = 0 , r = min(i , n - i);

            while(l < r)
            {
                int mid = l + r + 1 >> 1;
                if(f[i] - f[i - mid] * p[mid ]
                == g[n - i - 1] - g[n - i - mid -1] * p[mid ])l = mid;
                else r = mid - 1;
            }
            //cout << l <<endl;
            res = max(res , l * 2 + 1);

            l = 0 , r = min(i , n - i);

             while(l < r)
            {
                int mid = l + r + 1 >> 1;
                if(f[i] - f[i - mid ] * p[mid ]
                == g[n - i ] - g[n - i - mid ] * p[mid ])l = mid;
                else r = mid - 1;
            }
            res = max(res , l * 2);
        }
        cout << "Case "<<++t << ": " <<res <<endl; 
    }

    return 0;
}