回文子串的最大长度

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

using namespace std;

typedef unsigned long long ULL;

//因为需要给字符串添加#来构造成奇数长度，所以需要至少Double数据范围的空间
const int N = 3e6 + 10, k = 131;

ULL P[N], hl[N], hr[N];
char s[N];

//字符串哈希的模板函数
//h[]表示的是哈希数组，l表示的是区间左端点，r表示的是区间右端点
ULL get(ULL h[], int l, int r)
{
    return h[r] - h[l-1] * P[r-l+1];
}

int main()
{
    int T = 1;
    //使用逗号隔开，实现END结尾的输入操作
    while(scanf("%s", s+1), strcmp(s+1, "END"))
    {
        int len = strlen(s + 1);
        //初始化P数组，其用于存储指定长度的模数大小
        P[0] = 1;

        //在字符与字符之间填充
        for(int i = 2 * len; i > 0; i -= 2)
        {
            s[i] = s[i / 2];
            s[i - 1] = 'z' + 1;
        }

        len *= 2;

        for(int i = 1, j = len; i <= len; i ++, j --)
        {
            P[i] = P[i-1] * k;
            hl[i] = hl[i-1] * k + s[i];
            hr[i] = hr[i-1] * k + s[j];
        }

        int res = 0;
        //从第一个字母开始，遍历左右两边的回文串长度
        for(int i = 1; i <= len; i ++)
        {
            int l = 0, r = min(i - 1,len - i);
            while(l < r)
            {
                int mid = l + r + 1 >> 1;
                if(get(hl,i-mid,i-1) != get(hr,len - (i + mid) + 1,len - (i + 1) + 1))  r = mid - 1;
                else    l = mid;
            }
            if(s[i - l] <= 'z') res = max(res, l + 1);
            else    res = max(res, l);
        }
        printf("Case %d: %d\n", T++, res);
    }
    return 0;
}