后缀自动机二·重复旋律5

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 const int maxn = 1000010;
 4 char s[maxn];
 5 int maxlen[maxn<<1], minlen[maxn<<1], tr[maxn<<1][26], link[maxn<<1];
 6 int sz;
 7 
 8 int news(int maxl, int minl, int *trans, int lk){
 9     maxlen[sz] = maxl;
10     minlen[sz] = minl;
11     for(int i = 0; i < 26; i++){
12         if(trans == NULL) tr[sz][i] = -1;
13         else tr[sz][i] = trans[i];
14     }
15     link[sz] = lk;
16     return sz++;
17 }
18 int add(char ch, int u){
19     int c = ch - 'a';
20     int z = news(maxlen[u] + 1, -1, NULL, -1);
21     int v = u;
22     while(~v && tr[v][c] == -1){
23         tr[v][c] = z;
24         v = link[v];
25     }
26     if(v == -1){
27         minlen[z] = 1;
28         link[z] = 0;
29         return z;
30     }
31     int x = tr[v][c];
32     if(maxlen[v] + 1 == maxlen[x]){
33         minlen[z] = maxlen[x] + 1;
34         link[z] = x;
35         return z;
36     }
37     int y = news(maxlen[v] + 1, -1, tr[x], link[x]);
38     minlen[x] = maxlen[y] + 1;
39     link[x] = y;
40     minlen[z] = maxlen[y] + 1;
41     link[z] = y;
42     int w = v;
43     while(~w && tr[w][c] == x){
44         tr[w][c] = y;
45         w = link[w];
46     }
47     minlen[y] = maxlen[link[y]] + 1;
48     return z;
49 }
50 
51 int main(){
52     while(scanf("%s", s) != EOF){
53         int len = strlen(s);
54         sz = 0;
55         int pre = news(0, 0, NULL, -1);
56         for(int i = 0; i < len; i++){
57             pre = add(s[i], pre);
58         }
59         long long ans = 0;
60         for(int i = 1; i < sz; i++) ans += maxlen[i] - minlen[i] + 1;
61         printf("%lld
", ans);
62     }
63 }

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 const int maxn = 1000010;
 4 int len[maxn<<1], tr[maxn<<1][26], link[maxn<<1];
 5 int sz, last;
 6 long long ans;
 7 void init(){
 8     sz = last = 0;
 9     len[0] = 0, link[0] = -1;
10     memset(tr, -1, sizeof tr);
11     ++sz;
12 }
13 void sa(int c){
14     c = c - 'a';
15     int cur = sz++;
16     len[cur] = len[last] + 1;
17     int p;
18     for(p = last; ~p && tr[p][c] == -1; p = link[p]){
19         tr[p][c] = cur;
20     }
21     if(p == -1) link[cur] = 0;
22     else{
23         int q = tr[p][c];
24         if(len[p] + 1 == len[q]) link[cur] = q;
25         else{
26             int co = sz++;
27             len[co] = len[p] + 1;
28             for(int i = 0; i < 26; i++) tr[co][i] = tr[q][i];
29             link[co] = link[q];
30             for(; ~p && tr[p][c] == q; p = link[p]) tr[p][c] = co;
31             link[q] = link[cur] = co;
32         }
33     }
34     last = cur;
35     ans += len[cur] - len[link[cur]];
36 }
37 char s[maxn];
38 //long long solve(int u){
39 //    if(u == -1) return 0;
40 //    long long temp = 0;
41 //    for(int i = 0; i < 26; i++){
42 //        temp += solve(tr[u][i]);
43 //    }
44 //    return temp + 1;
45 //}
46 int main(){
47     while(scanf("%s", s) != EOF){
48         init();
49         ans = 0;
50         int len = strlen(s);
51         for(int i = 0; i < len; i++) sa(s[i]);
52         //ans = solve(0);
53         printf("%lld
", ans);
54     }
55 }