fork(10) download 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. const int maxn = 3e5 + 1, sigma = 26;
  6. int len[maxn], link[maxn], to[maxn][sigma];
  7. int slink[maxn], diff[maxn], series_ans[maxn];
  8. int sz, last, n;
  9. char s[maxn];
  10.  
  11. void init()
  12. {
  13.     s[n++] = -1;
  14.     link[0] = 1;
  15.     len[1] = -1;
  16.     sz = 2;
  17. }
  18.  
  19. int get_link(int v)
  20. {
  21.     while(s[n - len[v] - 2] != s[n - 1]) v = link[v];
  22.     return v;
  23. }
  24.  
  25. void add_letter(char c)
  26. {
  27.     s[n++] = c -= 'a';
  28.     last = get_link(last);
  29.     if(!to[last][c])
  30.     {
  31.         len[sz] = len[last] + 2;
  32.         link[sz] = to[get_link(link[last])][c];
  33.         diff[sz] = len[sz] - len[link[sz]];
  34.         if(diff[sz] == diff[link[sz]])
  35.             slink[sz] = slink[link[sz]];
  36.         else
  37.             slink[sz] = link[sz];
  38.         to[last][c] = sz++;
  39.     }
  40.     last = to[last][c];
  41. }
  42.  
  43. int main()
  44. {
  45.     ios::sync_with_stdio(0);
  46.     cin.tie(0);
  47.     init();
  48.     string s;
  49.     cin >> s;
  50.     int n = s.size();
  51.     int ans[n + 1];
  52.     memset(ans, 63, sizeof(ans));
  53.     ans[0] = 0;
  54.     for(int i = 1; i <= n; i++)
  55.     {
  56.         add_letter(s[i - 1]);
  57.         for(int v = last; len[v] > 0; v = slink[v])
  58.         {
  59.             series_ans[v] = ans[i - (len[slink[v]] + diff[v])];
  60.             if(diff[v] == diff[link[v]])
  61.                 series_ans[v] = min(series_ans[v], series_ans[link[v]]);
  62.             ans[i] = min(ans[i], series_ans[v] + 1);
  63.         }
  64.         cout << ans[i] << "\n";
  65.     }
  66.     return 0;
  67. }
  68.  
Success #stdin #stdout 0s 39856KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/xE2k6Y
minimal palindromic matching
language:
C++14 (gcc 8.3)
created:
9 years ago
visibility:
secret

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!