fork(22) download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. struct vertex
  6. {
  7.     vertex *to[2]={0,0};
  8.     vertex *up;
  9.  
  10.     vertex():up(0){}
  11.  
  12.     bool add(char t)
  13.     {
  14.         if(to[t]) return 0;
  15.         vertex *temp=new vertex;
  16.         temp->up=this;
  17.         to[t]=temp;
  18.         return 1;
  19.     }
  20. };
  21.  
  22. template<int delta> struct base
  23. {
  24. private:
  25.     vector<int> rad;
  26.     string text;
  27.     int i;
  28.     int n;
  29.  
  30.     vector<vertex*> link;
  31.     vertex *root;
  32.  
  33. public:
  34.  
  35.     base():i(1),n(0)
  36.     {
  37.         text.push_back('$');
  38.         rad.push_back(0);
  39.         root=new vertex;
  40.         link.push_back(root);
  41.     }
  42.  
  43.     bool add_letter(char t)
  44.     {
  45.         int r=0;
  46.         text+=t;
  47.         rad.push_back(0);
  48.         link.push_back(root);
  49.  
  50.         int s=i;
  51.         for(; i<=n+delta; i++)
  52.         {
  53.             link[i]=link[s-(i-s)];
  54.             rad[i]=rad[s-(i-s)];
  55.  
  56.             while(rad[i]-delta>n-i)
  57.                 rad[i]--,link[i]=link[i]->up;
  58.  
  59.             if(text[i-rad[i]]==text[i+rad[i]+1-delta])
  60.             {
  61.                 r=link[i]->add(t);
  62.                 link[i]=link[i]->to[t];
  63.                 rad[i]++;
  64.                 break;
  65.             }
  66.         }
  67.         n++;
  68.         return r;
  69.     }
  70. };
  71.  
  72. struct manacher
  73. {
  74. private:
  75.     base<0> even;
  76.     base<1> odd;
  77.  
  78. public:
  79.     int add_letter(char t)
  80.     {
  81.     	t-='a';
  82.         return odd.add_letter(t)+even.add_letter(t);
  83.     }
  84. } me;
  85.  
  86. main()
  87.  {
  88.     ios::sync_with_stdio(0);
  89.     cin.tie(0);
  90.     char t;
  91.     while((t=getchar())!='\n')
  92.         cout<<me.add_letter(t)<<' ';
  93.     cout<<"\n";
  94. }
  95.  
Success #stdin #stdout 0s 3476KB
comments (?)
stdin
copy 
abaaba
stdout
copy 
1 1 1 1 1 1
https://ideone.com/FybSWl
Дерево палиндромов. Алгоритм Манакера. O(n^2)
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!