fork(6) download
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. struct vertex
  6. {
  7. static const int k=16;
  8. int h;
  9. map<int,vertex*> to;
  10. vertex *up[k];
  11.  
  12. vertex():h(0){for(auto &it:up)it=this;}
  13.  
  14. bool add(char t)
  15. {
  16. if(to[t]) return 0;
  17. vertex *temp=new vertex;
  18. temp->h=this->h+1;
  19. temp->up[0]=this;
  20. for(int i=1;i<k;i++)
  21. temp->up[i]=temp->up[i-1]->up[i-1];
  22. to[t]=temp;
  23. return 1;
  24. }
  25.  
  26. vertex *up_to(int H)
  27. {
  28. H=h-H;
  29. vertex *ret=this;
  30. for(int i=k;i>=0;i--)
  31. if((1<<i)<=H)ret=ret->up[i],H-=1<<i;
  32. return ret;
  33. }
  34. };
  35.  
  36. template<int delta> struct base
  37. {
  38. private:
  39. vector<int> rad;
  40. string text;
  41. int i;
  42. int n;
  43.  
  44. vector<vertex*> link;
  45. vertex *root;
  46.  
  47. public:
  48.  
  49. base():i(1),n(0)
  50. {
  51. text.push_back('$');
  52. rad.push_back(0);
  53. root=new vertex;
  54. link.push_back(root);
  55. }
  56.  
  57. bool add_letter(char t)
  58. {
  59. int r=0;
  60. text+=t;
  61. rad.push_back(0);
  62. link.push_back(root);
  63.  
  64. int s=i;
  65. for(; i<=n+delta; i++)
  66. {
  67. link[i]=link[s-(i-s)]->up_to(n-i+delta);
  68. rad[i]=min(rad[s-(i-s)],n-i+delta);
  69.  
  70. if(text[i-rad[i]]==text[i+rad[i]+1-delta])
  71. {
  72. r=link[i]->add(t);
  73. link[i]=link[i]->to[t];
  74. rad[i]++;
  75. break;
  76. }
  77. }
  78. n++;
  79. return r;
  80. }
  81. };
  82.  
  83. struct manacher
  84. {
  85. private:
  86. base<0> even;
  87. base<1> odd;
  88.  
  89. public:
  90. int add_letter(char t)
  91. {
  92. return odd.add_letter(t)+even.add_letter(t);
  93. }
  94. } me;
  95.  
  96. main()
  97. {
  98. ios::sync_with_stdio(0);
  99. cin.tie(0);
  100. char t;
  101. int cur(0);
  102. while((t=getchar())!='\n')
  103. cout<<(cur+=me.add_letter(t))<<' ';
  104. cout<<"\n";
  105. }
  106.  
Success #stdin #stdout 0s 3480KB
stdin
abacaba
stdout
1 2 3 4 5 6 7