fork(17) download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. const int alph=256;
  6.  
  7. const int INF=1e9;
  8. const int MPOW=16;
  9. const int N=1<<MPOW-1;
  10. const int N2=N<<1;
  11. struct sg_tree
  12. {
  13.     int arr[N2];
  14.  
  15.     void build(vector<int> x,int n)
  16.     {
  17.         fill(arr,arr+N2,INF);
  18.         for(int i=0;i<n;i++)
  19.             arr[i+N]=x[i];
  20.         for(int i=N-1;i>0;i--)
  21.             arr[i]=min(arr[i<<1],arr[(i<<1)+1]);
  22.     }
  23.  
  24.     int get_min(int c,int cl,int cr,int l,int r)
  25.     {
  26.         if(l==cl && r==cr)
  27.             return arr[c];
  28.         if(l>r)
  29.             return INF;
  30.         int cm=cl+cr>>1;
  31.         return min(get_min(c<<1,cl,cm,l,min(r,cm)),get_min((c<<1)+1,cm+1,cr,max(l,cm+1),r));
  32.     }
  33.  
  34.     int get_min(int l,int r)
  35.     {
  36.         return get_min(1,0,N-1,l,r);
  37.     }
  38. };
  39.  
  40. pair<vector<int>,vector<int>> compute(string &s)
  41. {
  42.     int n=s.size();
  43.     int maxn=n+alph;
  44.  
  45.     vector<int> p(n),c(n),cnt(maxn,0);
  46.     for(int i=0;i<n;i++)
  47.         cnt[s[i]]++;
  48.     for(int i=1;i<maxn;i++)
  49.         cnt[i]+=cnt[i-1];
  50.     for(int i=0;i<n;i++)
  51.         p[--cnt[s[i]]]=i;
  52.     int cl=0;
  53.     c[p[0]]=cl;
  54.     for(int i=1;i<n;i++)
  55.     {
  56.         if(s[p[i]]!=s[p[i-1]])cl++;
  57.         c[p[i]]=cl;
  58.     }
  59.     vector<int> lcp(n,0);
  60.     for(int i=1;i<n;i++)
  61.         lcp[i]=c[p[i]]==c[p[i-1]];
  62.     vector<int> pn(n),cn(n),lcpn(n);
  63.     vector<int> rpos(n),lpos(n);
  64.     sg_tree rmq;
  65.     int k=1;
  66.     while(k<n)
  67.     {
  68.         fill(begin(cnt),end(cnt),0);
  69.         for(int i=0;i<n;i++)
  70.             rpos[c[p[i]]]=i;
  71.         for(int i=n-1;i>=0;i--)
  72.             lpos[c[p[i]]]=i;
  73.         for(int i=0;i<n;i++)
  74.         {
  75.             pn[i]=p[i]-k;
  76.             if(pn[i]<0)pn[i]+=n;
  77.         }
  78.         for(int i=0;i<n;i++)
  79.             cnt[c[i]]++;
  80.         for(int i=1;i<maxn;i++)
  81.             cnt[i]+=cnt[i-1];
  82.         for(int i=n-1;i>=0;i--)
  83.             p[--cnt[c[pn[i]]]]=pn[i];
  84.         cl=0;
  85.         cn[p[0]]=0;
  86.         for(int i=1;i<n;i++)
  87.         {
  88.             int m1=(p[i]+k)%n,m2=(p[i-1]+k)%n;
  89.             if(c[p[i]]!=c[p[i-1]] || c[m1]!=c[m2])cl++;
  90.             cn[p[i]]=cl;
  91.         }
  92.         rmq.build(lcp,n);
  93.         for(int i=1;i<n;i++)
  94.         {
  95.             int a=p[i],b=p[i-1];
  96.             if(c[a]!=c[b])
  97.                 lcpn[i]=lcp[lpos[c[a]]];
  98.             else
  99.             {
  100.                 int aa=(a+k)%n,bb=(b+k)%n;
  101.                 if(c[aa]==c[bb])
  102.                     lcpn[i]=k<<1;
  103.                 else
  104.                     lcpn[i]=k+rmq.get_min(lpos[c[bb]]+1,rpos[c[aa]]);
  105.             }
  106.             lcpn[i]=min(n,lcpn[i]);
  107.         }
  108.         copy(begin(cn),end(cn),begin(c));
  109.         copy(begin(lcpn),end(lcpn),begin(lcp));
  110.         k<<=1;
  111.     }
  112.     return {p,lcp};
  113. }
  114.  
  115.  
  116. struct suffix_tree
  117. {
  118.     struct edge
  119.     {
  120.         int from;
  121.         int to;
  122.         int next_vert;
  123.         int suffix_here;
  124.     };
  125.  
  126.     struct vertex
  127.     {
  128.         vector<edge> go;
  129.     };
  130.  
  131.     string str;
  132.     vector<vertex> data;
  133.  
  134.     static bool comp(const edge &b,const char &a)
  135.     {
  136.         return 1;
  137.     }
  138.  
  139.     void build(string &s)
  140.     {
  141.         // Получим суффиксный массив строки, а также массив lcp
  142.         pair<vector<int>,vector<int>> info=compute(s);
  143.         vector<int> p=info.first,lcp=info.second;
  144.  
  145.         int n=s.size();
  146.         str=s;
  147.  
  148.         // Будем хранить здесь стек рёбер, из которых мы ещё не вышли
  149.         vector<int> p_vert;
  150.         vector<int> p_edge;
  151.         vector<int> p_dist;
  152.  
  153.         // Добавим первую строку в дерево
  154.         vertex v;
  155.         edge e;
  156.         e.from=p[0];
  157.         e.to=n;
  158.         e.next_vert=-1;
  159.         e.suffix_here=p[0];
  160.         v.go.push_back(e);
  161.         data.push_back(v);
  162.  
  163.         p_vert.push_back(0);
  164.         p_edge.push_back(0);
  165.         p_dist.push_back(0);
  166.  
  167.         for(int i=1;i<n;i++)
  168.         {
  169.             int c_lcp=lcp[i];
  170.             // Поднимаемся до lcp.
  171.             while(p_dist.back()>c_lcp)
  172.             {
  173.                 // Найдём минимальный суффикс, покрывающий ребро для ответа на задачу. Опционально.
  174.                 edge &E=data[p_vert.back()].go[p_edge.back()];
  175.                 if(E.next_vert+1)
  176.                 {
  177.                     int m=data[E.next_vert].go.size();
  178.                     for(int j=0;j<m;j++)
  179.                         E.suffix_here=min(E.suffix_here,data[E.next_vert].go[j].suffix_here);
  180.                 }
  181.                 // Удалим ребро из стека. Больше мы в него не вернёмся
  182.                 p_vert.pop_back();
  183.                 p_edge.pop_back();
  184.                 p_dist.pop_back();
  185.             }
  186.             vertex v;
  187.             edge e;
  188.             int c_v=p_vert.back();
  189.             int c_e=p_edge.back();
  190.             int At=data[c_v].go[c_e].from+c_lcp-p_dist.back(); // Индекс для разделения ребра
  191.  
  192.             p_dist.push_back(c_lcp);
  193.  
  194.             // Ребро, которое надо добавить
  195.             e.next_vert=-1;
  196.             e.suffix_here=p[i];
  197.             e.from=p[i]+c_lcp;
  198.             e.to=n;
  199.  
  200.             // Либо добавляем ребро к вершине, либо разделяем текущее
  201.             if(At==data[c_v].go[c_e].from)
  202.             {
  203.                 data[c_v].go.push_back(e);
  204.                 p_vert.push_back(c_v);
  205.                 p_edge.push_back(data[c_v].go.size()-1);
  206.             }
  207.             else
  208.             {
  209.                 v.go.push_back(data[c_v].go[c_e]);
  210.                 v.go.back().from=At;
  211.                 v.go.push_back(e);
  212.                 data.push_back(v);
  213.                 data[c_v].go[c_e].next_vert=data.size()-1;
  214.                 data[c_v].go[c_e].to=At;
  215.                 p_vert.push_back(data.size()-1);
  216.                 p_edge.push_back(1);
  217.             }
  218.         }
  219.  
  220.         while(!p_dist.empty())
  221.         {
  222.             // Найдём минимальный суффикс, покрывающий ребро для ответа на задачу. Опционально.
  223.             edge &E=data[p_vert.back()].go[p_edge.back()];
  224.             if(E.next_vert+1)
  225.             {
  226.                 int m=data[E.next_vert].go.size();
  227.                 for(int j=0;j<m;j++)
  228.                     E.suffix_here=min(E.suffix_here,data[E.next_vert].go[j].suffix_here);
  229.             }
  230.  
  231.             // Удалим ребро из стека. Больше мы в него не вернёмся
  232.             p_vert.pop_back();
  233.             p_edge.pop_back();
  234.             p_dist.pop_back();
  235.         }
  236.     }
  237.  
  238.     int search_str(string &s)
  239.     {
  240.         int n=s.size();
  241.         int cur_v=0;
  242.         int cur_e;
  243.         char t;
  244.  
  245.         for(int i=0;i<n;)
  246.         {
  247.             if(cur_v==-1)break;
  248.             t=s[i];
  249.             int cur_e;
  250.             for(cur_e=0;cur_e<data[cur_v].go.size();cur_e++)
  251.                 if(str[data[cur_v].go[cur_e].from]>=t)break;
  252.             for(int j=data[cur_v].go[cur_e].from;i<n && j<data[cur_v].go[cur_e].to;j++,i++)
  253.                 if(str[j]!=s[i])
  254.                     i=n+1;
  255.             if(i==n)
  256.                 return data[cur_v].go[cur_e].suffix_here;
  257.             cur_v=data[cur_v].go[cur_e].next_vert;
  258.         }
  259.         return -1;
  260.     }
  261.  
  262.     int print(int x)
  263.     {
  264.         if(x==-1)return 0;
  265.         int ans=0;
  266.         for(int i=0;i<data[x].go.size();i++)
  267.             ans+=data[x].go[i].to-data[x].go[i].from+print(data[x].go[i].next_vert)-(data[x].go[i].to==str.size());
  268.         return ans;
  269.     }
  270. };
  271.  
  272. int main()
  273. {
  274.     ios::sync_with_stdio(0);
  275.     cin.tie(0);
  276.     string a;
  277.     cin>>a;
  278.     a+='#';
  279.     suffix_tree sf;
  280.     sf.build(a);
  281.     cout<<sf.print(0)<<endl;
  282. }
Success #stdin #stdout 0s 3628KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/5NAnYz
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!