#define _CRT_SECURE_NO_WARNINGS #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; #define INF (1<<29) #define rep(i,n) for(int i=0;i<(int)(n);i++) #define all(v) v.begin(),v.end() #define uniq(v) v.erase(unique(all(v)),v.end()) class SuffixArray { string text; vector sa; static bool eq(const vector &v, int idx1, int idx2, const vector &type) { if (v[idx1] != v[idx2])return false; int last = v.size() - 1; for (int i = 1;; i++) { if (v[idx1 + i] != v[idx2 + i])return false; if (idx1 + i == last || type[idx1 + i - 1] && !type[idx1 + i]) return idx2 + i == last || type[idx2 + i - 1] && !type[idx2 + i]; else if (idx2 + i == last || type[idx2 + i - 1] && !type[idx2 + i])return false; } return true; } template static inline void Lsort(const vector &v, const vector &type, vector &bucket, vector &rank_less) { for (int i = 0; i < (int)bucket.size(); i++) { if (bucket[i] > 0 && type[bucket[i] - 1]) { bucket[rank_less[v[bucket[i] - 1]]++] = bucket[i] - 1; if (erase)bucket[i] = -1; } } } template static inline void Ssort(const vector &v, const vector &type, vector &bucket, vector &rank_less_eq) { for (int i = bucket.size() - 1; i >= 0; i--) { if (bucket[i] > 0 && !type[bucket[i] - 1]) { bucket[--rank_less_eq[v[bucket[i] - 1]]] = bucket[i] - 1; if (erase)bucket[i] = -1; } } } static vector induced_sorting(const vector &v, int alpha) { vector bucket(v.size()); vector rank(alpha), c(alpha); vector type(v.size());//false=>S,true=>L vector lmsidx, lmsord; type.back() = true; for (int i = v.size() - 2; i >= 0; i--) { if (v[i] < v[i + 1])type[i] = false; else if (v[i] > v[i + 1])type[i] = true; else type[i] = type[i + 1]; } for (int i = 0; i < (int)v.size(); i++)rank[v[i]]++; for (int i = 1; i < alpha; i++)rank[i] += rank[i - 1]; //sorting LMS-substring fill(bucket.begin(), bucket.end(), -1); bool first = true; copy(rank.begin(), rank.end(), c.begin()); for (int i = 1; i < (int)v.size(); i++) { if (type[i - 1] && !type[i]) {//LMS if (first)first = false; else bucket[--c[v[i]]] = i; } } copy(rank.begin(), rank.begin() + alpha - 1, c.begin() + 1); c[0] = 0; bucket[c[v.back()]++] = v.size() - 1; Lsort(v, type, bucket, c); copy(rank.begin(), rank.end(), c.begin()); Ssort(v, type, bucket, c); for (int i = 0; i < (int)bucket.size(); i++) if (bucket[i] > 0)lmsidx.push_back(bucket[i]); if (!lmsidx.empty()) { lmsord.resize(lmsidx.size()); lmsord[0] = 0; for (int i = 1; i < (int)lmsidx.size(); i++) { if (eq(v, lmsidx[i - 1], lmsidx[i], type))lmsord[i] = lmsord[i - 1]; else lmsord[i] = lmsord[i - 1] + 1; } if (lmsord.back() + 1 != lmsord.size()) { vector lmssuffix; fill(bucket.begin(), bucket.end(), -1); for (int i = 0; i < (int)lmsidx.size(); i++) { if (lmsidx[i])bucket[lmsidx[i]] = lmsord[i]; } lmsidx.clear(); for (int i = 0; i < (int)bucket.size(); i++) { if (bucket[i] != -1) { lmssuffix.push_back(bucket[i]); lmsidx.push_back(i); } } vector lmssa(induced_sorting(lmssuffix, lmsord.back() + 1)); for (int i = 0; i < (int)lmsidx.size(); i++) { lmsord[i] = lmsidx[lmssa[i]]; } lmsidx.swap(lmsord); } lmsord.clear(); } //ended sorting LMS-substring fill(bucket.begin(), bucket.end(), -1); copy(rank.begin(), rank.end(), c.begin()); for (int i = lmsidx.size() - 1; i >= 0; i--) bucket[--c[v[lmsidx[i]]]] = lmsidx[i]; copy(rank.begin(), rank.begin() + alpha - 1, c.begin() + 1); c[0] = 0; bucket[c[v.back()]++] = v.size() - 1; Lsort(v, type, bucket, c); copy(rank.begin(), rank.end(), c.begin()); Ssort(v, type, bucket, c); return bucket; } public: SuffixArray(const string &s) { build(s); } const string& get_text()const { return text; } void build(const string &s) { text = s; vector v(s.size()); for (int i = 0; i < (int)s.size(); i++)v[i] = s[i] - 'a'; sa = induced_sorting(v, 27); } bool contain(const string &s)const { int a = -1, b = text.size() - 1; while (b - a > 1) { int c = (a + b) / 2; if (text.compare(sa[c], s.size(), s) < 0)a = c; else b = c; } return text.compare(sa[b], s.size(), s) == 0; } int lower_bound(string &s)const { int a = -1, b = text.size(); while (b - a > 1) { int c = (a + b) / 2; if (text.compare(sa[c], s.size(), s) < 0)a = c; else b = c; } return b; } int upper_bound(string &s)const { int a = -1, b = text.size(); while (b - a > 1) { int c = (a + b) / 2; if (text.compare(sa[c], s.size(), s) <= 0)a = c; else b = c; } return b; } string nth_suffix(int k)const { return text.substr(sa[k]); } int ord(int i)const { return sa[i]; } vector construct_lcp()const {//高さ配列を返す int n = text.size(); int h = 0; vector lcp(n - 1), rank(n); for (int i = 0; i < n; i++) rank[sa[i]] = i; lcp[0] = 0; for (int i = 0; i < n; i++) { if (rank[i] == 0)continue; int j = sa[rank[i] - 1]; if (h > 0)h--; for (; j + h < n&&i + h < n; h++) if (text[j + h] != text[i + h])break; lcp[rank[i] - 1] = h; } return lcp; } }; class SparseTableRMQ { int maxlog; std::vector log; std::vector M; public: SparseTableRMQ(const std::vector &a) { int n = a.size(); log.resize(n + 1); log[0] = 0; for (int i = 1, a = 0; i <= n; i++) { if ((1 << a + 1) < i)a++; log[i] = a; } maxlog = log[n] + 1; M.resize(n*maxlog); for (int i = 0; i < n; i++)M[i*maxlog] = a[i]; for (int j = 1; 1 << j <= n; j++) { for (int i = 0; i + (1 << j) - 1 < n; i++) { M[i*maxlog + j] = std::min(M[i*maxlog + j - 1], M[(i + (1 << j - 1))*maxlog + j - 1]); } } } int query(int i, int j)const {//[i,j)の最小値 int k = log[j - i]; return std::min(M[i*maxlog + k], M[(j - (1 << k))*maxlog + k]); } }; int main() { ios::sync_with_stdio(0); cin.tie(0); string s; cin >> s; int n = s.size(); string ss; ss += s; reverse(all(s)); ss += 'z' + 1; ss += s; SuffixArray sa(ss); vector ord(2 * n + 1); rep(i, 2 * n + 1)ord[sa.ord(i)] = i; vector lcp = sa.construct_lcp(); SparseTableRMQ rmq(lcp); int ans = 0; for (int i = 0; i < n; i++) { int a = min(ord[i], ord[2 * n - i]); int b = max(ord[i], ord[2 * n - i]); int c = rmq.query(a, b); if (2 * c - 1 == n)ans = max(ans, 2 * c - 1 - 2); else ans = max(ans, 2 * c - 1); if (0 <= i - c - 1 && i + c < n) { int x = min(ord[i + c], ord[2 * n - (i - c - 1)]); int y = max(ord[i + c], ord[2 * n - (i - c - 1)]); int z = rmq.query(x, y); ans = max(ans, 2 * (c + z) - 1); } if (0 <= i - c && i + c + 1 < n) { int x = min(ord[i + c + 1], ord[2 * n - (i - c)]); int y = max(ord[i + c + 1], ord[2 * n - (i - c)]); int z = rmq.query(x, y); ans = max(ans, 2 * (c + z) - 1); } } for (int i = 0; i + i < n; i++) { int a = min(ord[i + 1], ord[2 * n - (i)]); int b = max(ord[i + 1], ord[2 * n - (i)]); int c = rmq.query(a, b); if (2 * c == n)ans = max(ans, 2 * c - 2); else ans = max(ans, 2 * c); if (0 <= i - c - 1 && i + 1 + c < n) { int x = min(ord[i + 1 + c], ord[2 * n - (i - c - 1)]); int y = max(ord[i + 1 + c], ord[2 * n - (i - c - 1)]); int z = rmq.query(x, y); ans = max(ans, 2 * (c + z)); } if (0 <= i - c && i + 1 + c + 1 < n) { int x = min(ord[i + 1 + c + 1], ord[2 * n - (i - c)]); int y = max(ord[i + 1 + c + 1], ord[2 * n - (i - c)]); int z = rmq.query(x, y); ans = max(ans, 2 * (c + z)); } } cout << ans << endl; return 0; }