#include #define rep(i,n) for(int i = 0; i < (n); i++) using namespace std; typedef long long ll; struct RollingHash { static constexpr int M = 2; static constexpr long long MODS[M] = {999999937, 1000000007}; static constexpr long long BASE = 9973; vector powb[M], hash[M]; int n; RollingHash() {} RollingHash(const string& str) { init(str); } void init(const string& str) { n = str.size(); for (int k = 0; k < M; k++) { powb[k].resize(n + 1, 1); hash[k].resize(n + 1, 0); for (int i = 0; i < n; i++) { hash[k][i + 1] = (hash[k][i] * BASE + str[i]) % MODS[k]; powb[k][i + 1] = powb[k][i] * BASE % MODS[k]; } } } // get hash str[l,r) long long get(int l, int r, int k) { long long res = hash[k][r] - hash[k][l] * powb[k][r - l] % MODS[k]; if (res < 0) res += MODS[k]; return res; } }; bool match(RollingHash& rh1, int l1, int r1, RollingHash& rh2, int l2, int r2) { bool res = true; for (int k = 0; k < RollingHash::M; k++) { res &= rh1.get(l1, r1, k) == rh2.get(l2, r2, k); } return res; } int main(){ cin.tie(0); ios::sync_with_stdio(0); string S; cin >> S; int N = S.size(); RollingHash HS(S); reverse(S.begin(), S.end()); string T = S; RollingHash HT(T); reverse(S.begin(), S.end()); auto id = [&](int i) { return N - i; }; int ans = 0; rep(i,N) { // odd 回文 .. S[i] .. : .. の最大の長さ int len = 0; { auto f = [&](int x) { if(!(0 <= i - x) || !(i + x <= N)) return false; return match(HS, i - x, i, HT, id(i + 1 + x), id(i + 1)); }; int ok = 0, ng = N; while(ng - ok > 1) { int x = (ng + ok) / 2; (f(x) ? ok : ng) = x; } len = ok; } if(len + 1 + len < N) ans = max(ans, len + 1 + len); // S[i - len] .. S[i] .. S[i + len] // erase S[i - len - 1] if (i - len - 1 >= 0) { auto f = [&](int x) { if(!(0 <= i - len - 1 - x) || !(i + len + x <= N)) return false; return match(HS, i - len - 1 - x, i - len - 1, HT, id(i + len + x), id(i + len)); }; int ok = 0, ng = N; while(ng - ok > 1) { int x = (ng + ok) / 2; (f(x) ? ok : ng) = x; } if(ok + len + 1 + len + ok < N) ans = max(ans, ok + len + 1 + len + ok); } // erase S[i + len + 1] if(i + len + 1 < N) { auto f = [&](int x) { if(!(0 <= i - len - x) || !(i + len + 1 + x <= N)) return false; return match(HS, i - len - x, i - len, HT, id(i + len + 1 + 1 + x), id(i + len + 1 + 1)); }; int ok = 0, ng = N; while(ng - ok > 1) { int x = (ng + ok) / 2; (f(x) ? ok : ng) = x; } if(ok + len + 1 + len + ok < N) ans = max(ans, ok + len + 1 + len + ok); } if(i + 1 < N) { // even 回文 .. [S[i] S[i+1]] .. : len = .. の最大の長さ if(S[i] == S[i + 1]) { int len = 0; { auto f = [&](int x) { if(!(0 <= i - x) || !(i + 1 + 1 + x <= N)) return false; return match(HS, i - x, i, HT, id(i + 1 + 1 + x), id(i + 1 + 1)); }; int ok = 0, ng = N; while(ng - ok > 1) { int x = (ng + ok) / 2; (f(x) ? ok : ng) = x; } len = ok; } if(len + 1 + 1 + len < N) ans = max(ans, len + 1 + 1 + len); // S[i - len] .. S[i] S[i + 1] .. S[i + 1 + len] // erase S[i - len - 1] if(0 <= i - len - 1) { auto f = [&](int x) { if(!(0 <= i - len - 1 - x) || !(i + 1 + len + 1 + x <= N)) return false; return match(HS, i - len - 1 - x, i - len - 1, HT, id(i + 1 + len + 1 + x), id(i + 1 + len + 1)); }; int ok = 0, ng = N; while(ng - ok > 1) { int x = (ng + ok) / 2; (f(x) ? ok : ng) = x; } if(ok + len + 1 + 1 + len + ok < N) ans = max(ans, ok + len + 1 + 1 + len + ok); } // erase S[i + 1 + len + 1] if(i + 1 + len + 1 < N) { auto f = [&](int x) { if(!(0 <= i - len - x) || !(i + 1 + len + 1 + 1 + x <= N)) return false; return match(HS, i - len - x, i - len, HT, id(i + 1 + len + 1 + 1 + x), id(i + 1 + len + 1 + 1)); }; int ok = 0, ng = N; while(ng - ok > 1) { int x = (ng + ok) / 2; (f(x) ? ok : ng) = x; } if(ok + len + 1 + 1 + len + ok < N) ans = max(ans, ok + len + 1 + 1 + len + ok); } } else { // erase S[i] => .. [S[i-1] S[i+1]] .. if(0 <= i - 1 && S[i - 1] == S[i + 1]) { auto f = [&](int x) { if(!(0 <= i - 1 - x) || !(i + 1 + 1 + x <= N)) return false; return match(HS, i - 1 - x, i - 1, HT, id(i + 1 + 1 + x), id(i + 1 + 1)); }; int ok = 0, ng = N; while(ng - ok > 1) { int x = (ng + ok) / 2; (f(x) ? ok : ng) = x; } if(ok + 1 + 1 + ok < N) ans = max(ans, ok + 1 + 1 + ok); } // erase S[i + 1] => .. [S[i] S[i + 2]] .. if(i + 2 < N && S[i] == S[i + 2]) { auto f = [&](int x) { if(!(0 <= i - x) || !(i + 2 + 1 + x <= N)) return false; return match(HS, i - x, i, HT, id(i + 2 + 1 + x), id(i + 2 + 1)); }; int ok = 0, ng = N; while(ng - ok > 1) { int x = (ng + ok) / 2; (f(x) ? ok : ng) = x; } if(ok + 1 + 1 + ok < N) ans = max(ans, ok + 1 + 1 + ok); } } } } cout << ans << endl; }