后缀自动机三·重复旋律6

```  1 #include <iostream>
2 #include <cstdio>
3 #include <cmath>
4 #include <string>
5 #include <cstring>
6 #include <algorithm>
7 #include <limits>
8 #include <vector>
9 #include <stack>
10 #include <queue>
11 #include <set>
12 #include <map>
13 #include <bitset>
14 #include <unordered_map>
15 #include <unordered_set>
16 #define lowbit(x) ( x&(-x) )
17 #define pi 3.141592653589793
18 #define e 2.718281828459045
19 #define INF 0x3f3f3f3f
20 #define HalF (l + r)>>1
21 #define lsn rt<<1
22 #define rsn rt<<1|1
23 #define Lson lsn, l, mid
24 #define Rson rsn, mid+1, r
25 #define QL Lson, ql, qr
26 #define QR Rson, ql, qr
27 #define myself rt, l, r
28 #define pii pair<int, int>
29 #define MP(a, b) make_pair(a, b)
30 using namespace std;
31 typedef unsigned long long ull;
32 typedef unsigned int uit;
33 typedef long long ll;
34 const int maxN = 1e6 + 7;
35 int ans[maxN] = {0};
36 struct SAM
37 {
38     struct state
39     {
41     } st[maxN << 1];
42     int siz = 1, last, dp[maxN << 1];
43     void init()
44     {
45         siz = 1;
46         st[1].len = 0;
48         siz++;
49         last = 1;
50     }
51     int extend(int c)
52     {
53         int cur = siz++;
54         dp[cur] = 1;
55         st[cur].len = st[last].len + 1;
56         int p = last;
57         while (p != 0 && !st[p].next[c])
58         {
59             st[p].next[c] = cur;
61         }
62         if (p == 0)
63         {
65         }
66         else
67         {
68             int q = st[p].next[c];
69             if (st[p].len + 1 == st[q].len)
70             {
72             }
73             else
74             {
75                 int clone = siz++; dp[clone] = 0;
76                 st[clone].len = st[p].len + 1;
77                 memcpy(st[clone].next, st[q].next, sizeof(st[q].next));
79                 while (p != 0 && st[p].next[c] == q)
80                 {
81                     st[p].next[c] = clone;
83                 }
85             }
86         }
87         return last = cur;
88     }
89     vector<int> to[maxN << 1];
90     void dfs(int u)
91     {
92         for(int v : to[u])
93         {
94             dfs(v);
95             dp[u] += dp[v];
96         }
97         ans[st[u].len] = max(ans[st[u].len], dp[u]);
98     }
99     void slove()
100     {
101         for(int i=0; i<siz; i++) to[i].clear();
102         for(int i=2; i<siz; i++) to[st[i].link].push_back(i);
103         dfs(1);
104     }
105 } sam;
106 char s[maxN];
107 int main()
108 {
109     scanf("%s", s);
110     sam.init();
111     int len = (int)strlen(s);
112     for(int i=0; i<len; i++)
113     {
114         sam.extend(s[i] - ‘a‘);
115         ans[i + 1] = 0;
116     }
117     sam.slove();
118     for(int i=len - 1; i>=1; i--) ans[i] = max(ans[i], ans[i + 1]);
119     for(int i=1; i<=len; i++) printf("%d\n", ans[i]);
120     return 0;
121 }```

(0)
(0)