fork(117) download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define fpos adla
  6. const int inf = 1e9;
  7. const int maxn = 1e4;
  8. char s[maxn];
  9. map<int, int> to[maxn];
  10. int len[maxn], fpos[maxn], link[maxn];
  11. int node, pos;
  12. int sz = 1, n = 0;
  13.  
  14. int make_node(int _pos, int _len)
  15. {
  16.     fpos[sz] = _pos;
  17.     len [sz] = _len;
  18.     return sz++;
  19. }
  20.  
  21. void go_edge()
  22. {
  23.     while(pos > len[to[node][s[n - pos]]])
  24.     {
  25.         node = to[node][s[n - pos]];
  26.         pos -= len[node];
  27.     }
  28. }
  29.  
  30. void add_letter(int c)
  31. {
  32.     s[n++] = c;
  33.     pos++;
  34.     int last = 0;
  35.     while(pos > 0)
  36.     {
  37.         go_edge();
  38.         int edge = s[n - pos];
  39.         int &v = to[node][edge];
  40.         int t = s[fpos[v] + pos - 1];
  41.         if(v == 0)
  42.         {
  43.             v = make_node(n - pos, inf);
  44.             link[last] = node;
  45.             last = 0;
  46.         }
  47.         else if(t == c)
  48.         {
  49.             link[last] = node;
  50.             return;
  51.         }
  52.         else
  53.         {
  54.             int u = make_node(fpos[v], pos - 1);
  55.             to[u][c] = make_node(n - 1, inf);
  56.             to[u][t] = v;
  57.             fpos[v] += pos - 1;
  58.             len [v] -= pos - 1;
  59.             v = u;
  60.             link[last] = u;
  61.             last = u;
  62.         }
  63.         if(node == 0)
  64.             pos--;
  65.         else
  66.             node = link[node];
  67.     }
  68. }
  69.  
  70. int main()
  71. {
  72.     len[0] = inf;
  73.     string s;
  74.     cin >> s;
  75.     int ans = 0;
  76.     for(int i = 0; i < s.size(); i++)
  77.         add_letter(s[i]);
  78.     for(int i = 1; i < sz; i++)
  79.         ans += min((int)s.size() - fpos[i], len[i]);
  80.     cout << ans << "\n";
  81. }
  82.  
Success #stdin #stdout 0s 3508KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/sT8Vd1
suffix tree. Ukkonen O(n)
language:
C++ (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!