Height 数组应用 3。
子串等价于后缀的前缀,考虑容斥,用总数减去重复数量。
则答案为 n(n+1)2−n∑i=2heighti,因为 height 的定义是 LCP 长度。
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
int T, n;
char s[N];
int sa[N], rk[N], x[N], y[N];
int cnt[N];
void init_SA() {
int v = 128;
for (int i = 0; i <= v; i++) cnt[i] = 0;
for (int i = 1; i <= n; i++) ++cnt[x[i] = s[i]];
for (int i = 1; i <= v; i++) cnt[i] += cnt[i - 1];
for (int i = n; i >= 1; i--) sa[ cnt[x[i]]-- ] = i;
for (int len = 1; ; len <<= 1) {
int tot = 0;
for (int i = n - len + 1; i <= n; i++) y[++tot] = i;
for (int i = 1; i <= n; i++)
if (sa[i] > len) y[++tot] = sa[i] - len;
for (int i = 0; i <= v; i++) cnt[i] = 0;
for (int i = 1; i <= n; i++) ++cnt[x[i]];
for (int i = 1; i <= v; i++) cnt[i] += cnt[i - 1];
for (int i = n; i >= 1; i--) sa[ cnt[x[y[i]]]-- ] = y[i], y[i] = 0;
swap(x, y), tot = 0;
for (int i = 1; i <= n; i++) {
if (y[sa[i]] == y[sa[i - 1]] && y[sa[i] + len] == y[sa[i - 1] + len]) x[sa[i]] = tot;
else x[sa[i]] = ++tot;
}
v = tot;
if (v == n) break;
}
}
int ht[N];
void init_height() {
for (int i = 1; i <= n; i++) rk[sa[i]] = i;
for (int i = 1, j = 0, now = 0; i <= n; i++) {
if (rk[i] == 1) { ht[rk[i]] = 0; continue; }
j = sa[rk[i] - 1];
if (now) now--;
while (i + now <= n && j + now <= n && s[i + now] == s[j + now]) now++;
ht[rk[i]] = now;
}
}
long long ans = 0;
void solve() {
scanf("%s", s + 1), n = strlen(s + 1);
init_SA(), init_height();
ans = n * 1ll * (n + 1) / 2;
for (int i = 2; i <= n; i++) ans -= ht[i];
printf("%lld\n", ans);
}
int main() {
scanf("%d", &T);
while (T--) solve();
return 0;
}