fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define endl '\n'
  4. #define int long long
  5. #define ii pair<int,int>
  6. const int N = 5e5+5, M = 2e3+5, inf = 1e18, MOD = 1e9+7;
  7. int test, n, m, x, y, res, k, cnt, sum;
  8. int a[N], b[N], h1[N], h2[N], p[N];
  9.  
  10. signed main(){
  11.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  12.     string s1; char s[N];
  13.     cin >> n;
  14.     for (int i = 1; i <= n; ++i) cin >> s[i], h1[i] = (h1[i - 1] * 31 + s[i] - 'a' + 1) % MOD;
  15.     for (int i = n; i > 0; --i) h2[i] = (h2[i + 1] * 31 + s[i] - 'a' + 1) % MOD;
  16.     res = 1;
  17.     p[0] = 1;
  18.     for (int i = 1; i <= n; ++i) p[i] = (p[i - 1] * 31) % MOD;
  19.     for (int i = 2; i < n; ++i) {
  20.         int d = 1, c = min(i - 1, n - i);
  21.         while (d <= c) {
  22.             int mid = (d + c) >> 1;
  23.             x = (h1[i + mid] - h1[i] * p[mid] + MOD * MOD) % MOD;
  24.             y = (h2[i - mid] - h2[i] * p[mid] + MOD * MOD) % MOD;
  25.             if (x == y) res = max(res, mid << 1 | 1), d = mid + 1;
  26.             else c = mid - 1;
  27.         }
  28.         if (s[i] == s[i + 1]) {
  29.             res = max(res, (int) 2);
  30.             if (i + 1 == n) continue;
  31.             d = 1; c = min(i - 1, n - i - 1);
  32.             while (d <= c) {
  33.                 int mid = (d + c) >> 1;
  34.                 x = (h1[i + mid + 1] - h1[i + 1] * p[mid] + MOD * MOD) % MOD;
  35.                 y = (h2[i - mid] - h2[i] * p[mid] + MOD * MOD) % MOD;
  36.                 if (x == y) res = max(res, mid * 2 + 2), d = mid + 1;
  37.                 else c = mid - 1;
  38.             }
  39.         }
  40.     }
  41.     cout << res;
  42. }
  43.  
Success #stdin #stdout 0.01s 5372KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1
https://ideone.com/xy4aK5
language:
C++14 (gcc 8.3)
created:
2 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!