fork(6) download
copy 
  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
comments (?)
stdin
copy 
abacaba
stdout
copy 
1 2 3 4 5 6 7
https://ideone.com/j8NP5f
Дерево палиндромов. Двоичный подъём. O(nlogn)
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!