fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define int long long
  4. #define pii pair<int,int>
  5. int n;
  6. struct Hash {
  7.     static const int base1 = 1e9 + 975, base2 = 1e9 + 1357;
  8.     static const int mod1 = 1e9 + 5277, mod2 = 1e9 + 7277;
  9.     vector<int> pw1, pw2, h1, h2;
  10.     void assign(const string &s) {
  11.         int n = s.size();
  12.         pw1.assign(n+1,0);
  13.         pw2.assign(n+1,0);
  14.         h1.assign(n+1,0);
  15.         h2.assign(n+1,0);
  16.         pw1[0] = pw2[0] = 1;
  17.         for(int i = 1; i <= n; i++){
  18.             pw1[i] = (pw1[i-1] * 1LL * base1) % mod1;
  19.             pw2[i] = (pw2[i-1] * 1LL * base2) % mod2;
  20.             int v = s[i-1] - 'a' + 1;
  21.             h1[i] = (h1[i-1] * 1LL * base1 + v) % mod1;
  22.             h2[i] = (h2[i-1] * 1LL * base2 + v) % mod2;
  23.         }
  24.     }
  25.     pii get(int L, int R){
  26.         int x1 = (h1[R] - h1[L-1] * 1LL * pw1[R-L+1] % mod1 + mod1) % mod1;
  27.         int x2 = (h2[R] - h2[L-1] * 1LL * pw2[R-L+1] % mod2 + mod2) % mod2;
  28.         return {x1, x2};
  29.     }
  30. };
  31.  
  32. bool cmp(int mid, Hash &a, Hash &b){
  33. 	for(int i = 1; i + mid - 1 <= n; i++) 
  34. 	if(a.get(i, i + mid - 1) == b.get(n - (i + mid - 1) + 1, n - i + 1)) return 1;
  35. 	return 0;
  36.  
  37. }
  38.  
  39. signed main(){
  40.     ios::sync_with_stdio(false);
  41.     cin.tie(nullptr);
  42.  
  43.  
  44.     string s;
  45.     cin >> n >> s;
  46.  
  47.     Hash a, b;
  48.     a.assign(s);
  49.     reverse(s.begin(), s.end());
  50.     b.assign(s);
  51.  
  52.     int ans = 1;
  53.     int l = 1, r = n - n % 2;
  54.     while(l < r){
  55.         int mid = (l + r) / 2;
  56.         mid += mid % 2;
  57.         if(cmp(mid, a, b)){
  58.             l = mid;
  59.         } else  r = mid - 2;
  60.     }
  61.     ans = l;
  62.     l = 2, r = n + (n % 2 == 0);
  63.     while(l < r){
  64.         int mid = (l + r) / 2;
  65.         mid += (mid % 2 == 0);
  66.         if(cmp(mid, a, b)){
  67.             l = mid;
  68.         } else  r = mid - 2;
  69.     }
  70. 	ans = max(ans, l);
  71.     cout << ans;
  72.     return 0;
  73. }
  74.  
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
5
abacd
stdout
copy 
3
https://ideone.com/tx61ov
language:
C++14 (clang 8.0)
created:
1 day 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!