fork(1) download 
  1. #include <iostream>
  2. #include <utility>
  3. #include <vector>
  4. #include <algorithm>
  5. #include <numeric>
  6. #include <map>
  7. #include <unordered_set>
  8. #include <iostream>
  9. #include <utility>
  10. #include <vector>
  11. #include <algorithm>
  12. #include <numeric>
  13. #include <map>
  14. #include <unordered_set>
  15. #include <unordered_map>
  16. #include <queue>
  17. #include <set>
  18. #include <stack>
  19. #include <fstream>
  20. #include <ext/pb_ds/assoc_container.hpp>
  21. #include <ext/pb_ds/tree_policy.hpp>
  22. #include <bitset>
  23. #include <sstream>
  24. #include <ext/rope>
  25. #include <ctime>
  26. #include <random>
  27. #include <cstdlib>
  28. #include <complex>
  29.  
  30. using namespace std;
  31. using namespace __gnu_pbds;
  32. using namespace __gnu_cxx;
  33.  
  34. /* clang-format off */
  35.  
  36. /* TYPES  */
  37. #define ll long long
  38. #define pii pair<int, int>
  39. #define pll pair<long long, long long>
  40. #define vi vector<int>
  41. #define vll vector<long long>
  42. #define vpii vector<pair<int, int>>
  43. #define vpii vector<pair<int, int>>
  44. #define vvpii vector<vector<pair<int, int>>>
  45. #define vpll vector<pair<long long, long long>>
  46. #define vvpll vector<vector<pair<long long, long long>>>
  47. #define vvi vector<vector<int>>
  48. #define vvll vector<vector<long long>>
  49. #define mii map<int, int>
  50. #define si set<int>
  51. #define sc set<char>
  52.  
  53.  
  54.  
  55. /* FUNCTIONS */
  56. #define feach(el, v) for(auto &el: v)
  57. #define rep(i, n) for(int i=0;i<n;i++)
  58. #define reprv(i, n) for(int i=n-1;i>=0;i--)
  59. #define reps(i, s, e) for(int i=s;i<e;i++)
  60. #define reprve(i, e, s) for(int i=e;i>=s;i--)
  61. #define repe(x, y) for (auto &x: y)
  62. #define repe2(x, a, y) for (auto &[x,a]: y)
  63.  
  64. typedef tree<int, null_type, less<>, rb_tree_tag, tree_order_statistics_node_update> oSet;
  65.  
  66. const int MAXLEN = 100020;
  67.  
  68. struct state {
  69.     int len, link;
  70.     map<char, int> next;
  71. };
  72.  
  73. state st[MAXLEN * 2];
  74. int sz, last;
  75.  
  76. void init() {
  77.     sz = 1, last = 0;
  78.     st[0].len = 0, st[0].link = -1;
  79. }
  80.  
  81. void extend(char c) {
  82.     int cur = sz++;
  83.     st[cur].len = st[last].len + 1;
  84.  
  85.     int p = last;
  86.     while (p != -1 && !st[p].next.count(c)) st[p].next[c] = cur, p = st[p].link;
  87.  
  88.     last = cur;
  89.     if (p == -1) return void(st[cur].link = 0);
  90.  
  91.     int q = st[p].next[c];
  92.     if (st[p].len + 1 == st[q].len) return void(st[cur].link = q);
  93.  
  94.     int clone = sz++;
  95.     st[clone].len = st[p].len + 1, st[clone].next = st[q].next, st[clone].link = st[q].link;
  96.  
  97.     while (p != -1 && st[p].next[c] == q) st[p].next[c] = clone, p = st[p].link;
  98.     st[q].link = st[cur].link = clone;
  99. }
  100.  
  101. void build(string &s) { init(); repe(ch, s) extend(ch); }
  102.  
  103.  
  104. int main() {
  105.     string s; cin >> s; build(s);
  106.     int n = s.size();
  107.  
  108.     vll ans(n + 2, 0);
  109.     reps(i, 1, sz) ++ans[st[st[i].link].len + 1], --ans[st[i].len + 1];
  110.  
  111.     ll curr = 0;
  112.     reps(i, 1, n + 1) curr += ans[i], cout << curr << " ";
  113. }
Success #stdin #stdout 0.01s 14492KB
comments (?)
stdin 
dfgfglrisgdsdgskd
stdout 
8 15 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1
https://ideone.com/ehPr3R
language:
C++14 (gcc 8.3)
created:
154 days 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!