fork(9) 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
stdin
Standard input is empty
stdout
Standard output is empty