纯粹是记录一下做法，并不是题解那么高大上的东西

题目描述

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

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

输入格式

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

输入以一个以字符串 END 开头的行表示输入终止。

输出格式

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

每个输出占一行。

输入样例

abcbabcbabcba
abacacbaaaab
END

输出样例

Case 1: 13
Case 2: 6

做法与y总视频中完全一致。

C++ 代码

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

using namespace std;

typedef unsigned long long ULL;         //用unsigned long long 可以实现自然上溢，便是模2^64

const int N = 2e6 + 10, base = 131;     //经验值，模数为2^64, 进制为131或13331

ULL hl[N], hr[N], p[N] = {1};           //hl[N]记录从左到右的哈希，hr[N]记录从右到左的哈希
char str[N]; 
int round = 1;

ULL get(ULL h[], int l, int r)      //计算子串的哈希值
{
    return h[r] - h[l - 1] * p[r - l + 1];
}

int main()
{
    for(int i = 1; i < N; ++i) p[i] = p[i - 1] * base;

    while(cin >> str + 1 && strcmp(str + 1, "END"))
    {
        int res = 0;
        int n = strlen(str + 1);

        for(int i = 2 * n; i > 0; i -= 2)   
        {
            str[i] = str[i / 2];
            str[i - 1] = '#';
        }

        n *= 2;         //以上是拓宽字符串，使每个字符中间用一个'#'隔开，这样减少一步判断

        for(int i = 1, j = n; i <= n; ++i, --j)         //预处理
        {
            hl[i] = hl[i - 1] * base + str[i];
            hr[i] = hr[i - 1] * base + str[j];
        }

        for(int i = 1; i <= n; ++i)         //重点，字符串哈希+二分
        {
            int l = 0, r = min(i - 1, n - i);       //二分的边界，不包含当前位置的字符，所以长度为 0~xxx
            while(l < r)
            {
                int mid = l + r + 1 >> 1;
                if(get(hl, i - mid, i - 1) != get(hr, n + 1 - i - mid, n - i)) r = mid - 1;     //传参时注意，hl数组传入正序序号
                else l = mid;                                                                   //hr数组传入逆序序号
            }

            if(str[i - l] == '#') res = max(res, l);            // 判断最长回文子串边界，进行相应处理
            else res = max(res, l + 1);  
        }

        cout << "Case " << round++ << ": " << res << endl;
    }
    return 0;
}