fork(2) download 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. const int maxn = 1e5 + 1;
  6.  
  7. int s[maxn], to[maxn][26], len[maxn], link[maxn];
  8. int n, sz, last;
  9.  
  10. void init()
  11. {
  12.     s[n++] = -1;
  13.     link[0] = 1;
  14.     len[1] = -1;
  15.     sz = 2;
  16. }
  17.  
  18. int get_link(int v)
  19. {
  20.     while(s[n - len[v] - 2] != s[n - 1]) v = link[v];
  21.     return v;
  22. }
  23.  
  24. int add_letter(char c)
  25. {
  26.     s[n++] = c -= 'a';
  27.     last = get_link(last);
  28.     if(!to[last][c])
  29.     {
  30.         len[sz] = len[last] + 2;
  31.         link[sz] = to[get_link(link[last])][c];
  32.         to[last][c] = sz++;
  33.     }
  34.     last = to[last][c];
  35.     return len[last];
  36. }
  37.  
  38. int main()
  39. {
  40.     ios::sync_with_stdio(0);
  41.     cin.tie(0);
  42.     init();
  43.     int n;
  44.     cin >> n;
  45.     string s;
  46.     cin >> s;
  47.     int ans = 0;
  48.     for(auto c: s)
  49.         ans = max(ans, add_letter(c));
  50.     cout << ans;
  51.     return 0;
  52. }
  53.  
Success #stdin #stdout 0s 14560KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/ePes8E
language:
C++14 (gcc 8.3)
created:
10 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!