1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
|
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
typedef pair<int, int> PII;
typedef long long LL;
const int N = 100010;
int n;
int sa[N], rk[N], cnt[N], oldrk[N << 1], id[N], px[N];
char s[N];
int ht[N];
PII stk[N];
int tt;
inline bool cmp(int x, int y, int k) {
return oldrk[x] == oldrk[y] && oldrk[x + k] == oldrk[y + k];
}
void SA() {
int i, p = 0, k, m = 300;
memset(cnt, 0, sizeof cnt);
for (i = 1; i <= n; i++) cnt[rk[i] = s[i]]++;
for (i = 1; i <= m; i++) cnt[i] += cnt[i - 1];
for (i = n; i >= 1; i--) sa[cnt[rk[i]]--] = i;
for (k = 1; k < n; k <<= 1, m = p) {
for (p = 0, i = n ; i > n - k; i--) id[++p] = i;
for (i = 1;i <= n; i++){
if (sa[i] > k) id[++p] = sa[i] - k;
}
memset(cnt, 0, sizeof cnt);
for (i = 1; i <= n; i++) cnt[px[i] = rk[id[i]]]++;
for (i = 1; i <= m; i++) cnt[i] += cnt[i - 1];
for (i = n; i >= 1; i--) sa[cnt[px[i]]--] = id[i];
memcpy(oldrk, rk, sizeof rk);
for (p = 0, i = 1; i <= n; i++){
rk[sa[i]] = cmp(sa[i], sa[i - 1], k) ? p : ++p;
}
}
for (int i = 1; i <= n; i++) {
if (rk[i] == 1) continue;
int k = max(ht[rk[i - 1]] - 1, 0);
while (i + k <= n && s[i + k]== s[sa[rk[i] - 1] + k]) k++;
ht[rk[i]] = k;
}
}
LL f(LL x) { // 出现次数为x的贡献
return x * (x + 1) / 2;
}
int main() {
scanf("%s", s + 1);
n = strlen(s + 1);
SA();
LL res = 0;
for (int i = 1; i <= n; i++) {
res += n - sa[i] + 1 - max(ht[i], ht[i + 1]);
}
// 单调栈维护非递减height值(first)，并存大于栈顶的height值，所能到达的最左边界(second).
for (int i = 1; i <= n + 1; i++) {
int left = i; // 初始化大于栈顶的height值，所能到达的最左边界为下标i
while (tt && stk[tt].first > ht[i]) {
int num = i - stk[tt].second + 1; // lcp>ht[i]的区间长度，说明这一段贡献了长度为height[i]的子串
int len = stk[tt].first - max(ht[i], stk[tt - 1].first);
res += f(num) * len;
left = min(left, stk[tt].second); // 更新LCP > 栈顶的height值的左边界
tt--;
}
stk[++tt] = {ht[i], left};
}
cout << res << endl;
return 0;
}
|