Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- #define fi first
- #define se second
- #define pf push_front
- #define pb push_back
- #define mk make_pair
- #define all(c) (c).begin(), (c).end()
- #define sz(x) (int)x.size()
- #define SWS ios_base::sync_with_stdio(false)
- #define rfile freopen("input.txt", "r", stdin)
- #define wfile freopen("output.txt", "w", stdout)
- #define files rfile; wfile
- typedef long long ll;
- typedef long double ld;
- const int Z = (int)1e5 + 111;
- const int inf = (int)1e9 + 111;
- const ll llinf = (ll)1e18 + 5;
- const int MOD = (int)1e9 + 7;
- vector<int> dd1 (string s) {
- int n = sz(s);
- vector<int> d1 (n);
- int l=0, r=-1;
- for (int i=0; i<n; ++i) {
- int k = (i>r ? 0 : min (d1[l+r-i], r-i)) + 1;
- while (i+k < n && i-k >= 0 && s[i+k] == s[i-k]) ++k;
- d1[i] = k--;
- if (i+k > r)
- l = i-k, r = i+k;
- }
- return d1;
- }
- vector <int> dd2 (string s) {
- int n = sz(s);
- vector<int> d2 (n);
- int l=0, r=-1;
- for (int i=0; i<n; ++i) {
- int k = (i>r ? 0 : min (d2[l+r-i+1], r-i+1)) + 1;
- while (i+k-1 < n && i-k >= 0 && s[i+k-1] == s[i-k]) ++k;
- d2[i] = --k;
- if (i+k-1 > r)
- l = i-k, r = i+k-1;
- }
- return d2;
- }
- int main () {
- srand(time(0));
- //files;
- string s, t;
- cin >> s;
- t = s;
- //reverse(all(t));
- s.pop_back();
- s = t + s;
- //cout << s << '\n';
- vector <int> ans;
- vector <int> d1 = dd1(s), d2 = dd2(s);
- for (int i = 0; i < d1.size(); i++) {
- ans.pb(d1[i] * 2 - 1);
- ans.pb(d2[i] * 2);
- }
- int aans = 0;
- for (int i = 0; i < ans.size(); i++)
- if (ans[i] <= t.length()) {
- aans = max(aans, ans[i]);
- }
- cout << aans;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement