题目描述

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

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

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

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

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

每个输出占一行。

样例

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

算法1

利用单调性 $O(n)$

设以r结尾的最大回文子串长度为f(r)，显然有f(r+1)-f(r)<=2。即每增加一个字符，最大回文串的长度最多增加2。

时间复杂度

maxi单调增加，O(N)

C++ 代码

#include <iostream>
#include <set>
#include <map>
#include <algorithm>
#include <climits>
#include <vector>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <string>
#include <utility>
#include <cstring>
#include <queue>
#include <cmath>
#include <iomanip>
#include <bitset>

#define LL long long
#define fi first
#define se second
#define pii pair<int, int>
#define pll pair<LL, LL>
#define pdd pair<double, double>
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
#define length(p1, p2) ((p1.fi-p2.fi)*(p1.fi-p2.fi)+(p1.se-p2.se)*(p1.se-p2.se))
#define ith(state, i) (state & (1 << i)) 

using namespace std;

class PrimeSelector {public: vector<bool> prime; set<int> primes; int n; PrimeSelector(int n): n(n), prime(n+1, true) { prime[0] = prime[1] = false; for (int i = 1; i * i <= n; i++) { if (!prime[i]) continue; for (int j = i * i; j <= n; j += i) prime[j] = false; } for (int i = 2; i <= n; i++) if (prime[i]) primes.insert(i); } };
LL kpow(LL a, LL b) { LL c = 1; while (b) { if (b & 1) c = c * a; a = a * a; b >>= 1; } return c;}
LL kpow(LL a, LL b, LL mod) { LL c = 1 % mod; while (b) { if (b & 1) c = c * a % mod; a = a * a % mod; } return c;}
LL rev(LL a, LL mod) { return kpow(a, mod-2, mod); }
map<LL, LL> splitPrime(LL x, vector<bool>& prime) { map<LL, LL> res; for (int i = 2; i * i <= x; i++) { if (!prime[i]) continue; while (x % i == 0) res[i]++, x /= i; if (res[i] == 0) res.erase(i); } if (prime[x]) res[x] = 1; return res; }
map<LL, LL> splitPrime(LL x, set<int>& prime) { map<LL, LL> res; for (auto i: prime) { if (i * i > x) break; while (x % i == 0) res[i]++, x /= i; if (res[i] == 0) res.erase(i); } if (prime.find(x) != prime.end()) res[x] = 1; return res; }
map<LL, LL> mul(const map<LL, LL>& m1, const map<LL, LL>& m2) { map<LL, LL> res; for (auto& p: m1) res[p.fi] = p.se; for (auto& p: m2) { res[p.fi] += p.se; if (res[p.fi] == 0) res.erase(p.fi); } return res; }
map<LL, LL> rev(map<LL, LL> m) { map<LL, LL> res; for (auto& p: m) res[p.fi] = -p.se; return res; }
LL m2L(map<LL, LL> m) { LL res = 1; for (auto& p: m) res *= kpow(p.fi, p.se); return res; }
#define W 1000000000LL
vector<LL> n2B(LL n) { vector<LL> res; if (n == 0) return {0LL};  while (n) { res.push_back(n % W); n /= W; } reverse(res.begin(), res.end()); return res; }
void simple(vector<LL>& res) { while (!res.empty() && res.back() == 0LL) res.pop_back(); if (res.empty()) res.push_back(0LL); }
vector<LL> add(const vector<LL>& b1, const vector<LL>& b2) { vector<LL> res; res.reserve(max(b1.size(), b1.size())+1); LL up = 0LL; int i = b1.size()-1, j = b2.size()-1; while (i >= 0 && j >= 0) { LL b = b1[i--] + b2[j--] + up; res.push_back(b % W); up = b / W; } while (i >= 0) { LL b = b1[i--] + up; res.push_back(b % W); up = b / W; } while (j >= 0) { LL b = b2[j--] + up; res.push_back(b % W); up = b / W; } if (up) res.push_back(up); simple(res); reverse(res.begin(), res.end()); return res; }
vector<LL> mul(const vector<LL>& b1, LL i) { vector<LL> res; res.reserve(b1.size()+1); LL up = 0; for (int j = b1.size()-1; j >= 0; j--) { LL b = b1[j] * i + up; res.push_back(b % W); up = b / W; } if (up) res.push_back(up); simple(res); reverse(res.begin(), res.end()); return res; }
void shift(vector<LL>& b1, LL i) { if (b1.size() == 1 && b1[0] == 0LL) return; while (i--) { b1.push_back(0); } }
vector<LL> mul(const vector<LL>& b1, const vector<LL>& b2) { if (b1.size() < b2.size()) return mul(b2, b1); vector<LL> res; res.reserve(b1.size()+b2.size()+1); res.push_back(0); if (b2.size() == 1 && b2[0] == 0) return res; int shi = 0; for (int j = b2.size()-1; j >= 0; j--) { vector<LL> r = mul(b1, b2[j]); shift(r, shi++); res = add(res, r); } return res; }
vector<LL> m2B(const map<LL, LL>& m) { if (m.empty()) return {1}; vector<LL> res; res.reserve(100); res.push_back(1); for (auto& p: m) { vector<LL> r = n2B(p.fi); for (int i = 0; i < p.se-1; i++) r = mul(r, n2B(p.fi)); res = mul(res, r); } return res; }
struct DSU { vector<int> par; vector<int> sz; int n; DSU(int n) : par(n+1), sz(n+1), n(n) { for (int i = 0; i <= n; i++) sz[i] = 1, par[i] = i; } int find(int x) { if (x == par[x]) return x; return find(par[x]); } void uni(int x, int y) { int px = find(x), py = find(y); if (px == py) return; if (sz[px] < sz[py]) return uni(py, px); par[py] = px, sz[px] += sz[py]; } };
template <class T> struct VHash { size_t operator () (const vector<T>& v) const { size_t res = 0; for (T i: v) res ^= i; return res; } };
struct SHash { vector<LL> presum; vector<LL> po; LL seed; LL mod; SHash(LL n, LL seed, LL mod): seed(seed), mod(mod), presum(n+1, 0), po(n+1, 1) {} void load(const string& s) { for (int i = 1; i <= (int)s.size(); i++) { presum[i] = (presum[i-1] * seed + s[i-1]) % mod; po[i] = po[i-1] * seed % mod; } } LL get(int i, int j) { if (i > j) return 0; return (presum[j] - presum[i-1] * po[j-i+1] % mod + mod) % mod; } };


#define MAXN 1000005
#define eps 1e-4

string s;
SHash h(MAXN, 113, 1000000007);
SHash rh(MAXN, 113, 1000000007);

int main() {
    fastio;
    s.reserve(MAXN);
    cin >> s;
    int t = 0;
    while (s != "END") {
        int N = s.size();
        int maxi = 1;
        h.load(s);
        reverse(s.begin(), s.end());
        rh.load(s);
        for (int r = 1; r <= N; r++) {
            if (r - maxi >= 1 && h.get(r-maxi, r) == rh.get(N+1-r, N+1-r+maxi)) maxi++;
            if (r - maxi - 1 >= 1 && h.get(r-maxi-1, r) == rh.get(N+1-r, N+1-r+maxi+1)) maxi += 2;
        }
        cout << "Case " << ++t << ": " << maxi << endl;
        cin >> s;
    }
    return 0;
}