题面描述
给定字符串集合，求只属于该字符串的本质不同的非空子串的个数
题解
难度一般，建一个广义 \(SAM\) 在 \(Parent\) 树上对 \(endpos\) 全部属于同一个字符串的统计即可
关键是下面的错误和解决方法
大部分直接按照 \(maxlen\) 拓扑序会 \(WA\)，是因为如果字符串具有相同前缀则在广义 \(SAM\) 中会出现 \(maxlen(parent(A))= maxlen(A)\)
主要是因为大部分广义 \(SAM\) 的写法每次都必须新建一个 \(np\) 节点，但实际上这个 \(np\) 节点所表示的原串的前缀有可能在 \(SAM\) 上出现了，但由于 \(Parent\) 树的性质两者间有边相连，导致了 \(maxlen\) 非严格单调递增的父子关系，可以通过 \(\lbrace ab, abc\ \rbrace\) 体会一下 所以当 \(maxlen\) 相同时，后加入的节点要靠后
但是按照我这种写法又 \(WA\) 第 \(2\) 个点，是由于新建的 \(nq\) 节点应该继承 \(np\) 节点的某一个 \(endpos\) 而不是 \(q\) 节点的 \(endpos\)
原因是我们会认为在某次加入操作时 \(nq\) 的加入顺序晚于 \(np\)，导致 \(np\) 最后不能及时更新 \(nq\)，那么一开始我们就应该将更晚的 \(np\) 的某一个 \(endpos\) 赋值给 \(nq\) 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
using namespace std;
const int N = 2e5+5;
typedef long long int64;
int last = 1, tot = 1, pre, pos[N], len[N], fa[N], ch[N][26];
int tax[N], p[N];
int64 ans[N];
inline void insert(int c, int p)
{
int cur = ++tot, pre = last; last = cur;
len[cur] = len[pre]+1; pos[cur] = p;
while(pre&&!ch[pre][c]) ch[pre][c] = cur, pre = fa[pre];
if(!pre) return void(fa[cur] = 1);
int x = ch[pre][c];
if(len[pre]+1 == len[x]) return void(fa[cur] = x);
int y = ++tot; fa[y] = fa[x]; pos[y] = p;
fa[x] = fa[cur] = y; len[y] = len[pre]+1;
memcpy(ch[y], ch[x], sizeof(ch[x]));
while(pre&&ch[pre][c] == x) ch[pre][c] = y, pre = fa[pre];
}
int n;
char s[N];
int main()
{
scanf("%d", &n);
for(int i = 1; i <= n; ++i)
{
last = 1; scanf("%s", s);
for(int k = 0; s[k]; ++k) insert(s[k]-'a', i);
}
for(int i = 1; i <= tot; ++i) ++tax[len[i]];
for(int i = 1; i <= tot; ++i) tax[i] += tax[i-1];
for(int i = tot; i; --i) p[tax[len[i]]--] = i;
for(int i = tot; i; --i) if(pos[fa[p[i]]] != pos[p[i]]) pos[fa[p[i]]] = 0;
for(int i = 1; i <= tot; ++i) ans[pos[i]] += len[i]-len[fa[i]];
for(int i = 1; i <= n; ++i) printf("%lld\n", ans[i]);
return 0;
}