这道题有两种做法，一种是马拉车（manager）算法，是O(n)的；一种是二分+哈希，是O(n log n)的。实际上两种都可以通过，而后者更加简单，且本题希望考察后者，所以我暂时只讲解后一种算法。

要使用二分，必须保证答案具有单调性，就是说如果len满足条件，那么len-1也一定满足条件。但事实上这题并不具有这个特点，不过我们可以进行一个变形：把奇数长度和偶数长度分开考虑。这是因为，如果有len(len >= 2)长度的回文串，那么把它“掐头去尾”后得到的这个len-2长度的串一定也是回文串。

上面讲了二分部分，下面我们呢来讲一下如何利用哈希判断回文串。回文串可以理解为一个串倒过来和原来是一样的，于是我们在原串上正过来反过来各进行一次哈希，然后利用前缀和的思想进行查询，O(1)判断一个串正过来和反过来是不是一样的，这样查询n次就可以判断是否有长度为len的结果了。

#include <bits/stdc++.h>


using namespace std;


typedef unsigned long long ULL; // 无符号类型溢出相当于有自动取模


int n;
ULL hshcode[1000010], hshcode_rev[1000010];
ULL val[1000010]; // val[i]是13331的i次方，这个用来进行前缀和思想的查询


void prework(string str) { // 主要是求正反两套哈希值和val数组
    hshcode[0] = hshcode[n + 1] =
      hshcode_rev[0] = hshcode[n + 1] = 0;
    for (int i = 1; i <= n; ++i) {
        hshcode[i] = hshcode[i - 1] * 13331 + str[i];
    }
    for (int i = n; i >= 1; --i) {
        hshcode_rev[i] = hshcode_rev[i + 1] * 13331 + str[i];
    }
    val[0] = 1;
    for (int i = 1; i <= n; ++i) {
        val[i] = val[i - 1] * 13331;
    }
}


bool is_palindrome_substr(int l, int r) { // 判断回文，代码核心，建议多读几遍
    return hshcode[r] - val[r - l + 1] * hshcode[l - 1] ==
      hshcode_rev[l] - val[r - l + 1] * hshcode_rev[r + 1];
}

bool check(int len) {
    for (int i = 1; i <= n - len + 1; ++i) {
        if (is_palindrome_substr(i, i + len - 1)) {
            return 1;
        }
    }
    return 0;
}


int main(void) {
    string str;
    int case_id = 0;
    while (((cin >> str), str) != "END") {
        cout << "Case " << ++case_id << ": ";
        n = str.size();
        str = '$' + str; // 变成了1起点
        prework(str);
        int l = 1, r = (n + 1) / 2, res = -1; // 二分边界，如果不理解可以手撸几个数据模拟一下看最大最小值
        while (l <= r) {
            int mid = (l + r) / 2;
            int even = mid * 2, odd = mid * 2 - 1;
            if (check(even)) { // 奇数一定比偶数小，而我们要尽量大，所以先考虑偶数
                res = even;
                l = mid + 1;
            } else if (check(odd)) {
                res = odd;
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        cout << res << endl; 
    }
    return 0;
}