fork(102) download
  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
stdin
Standard input is empty
stdout
0