[USACO17DEC]Standing Out from the Herd

题面描述

给定字符串集合，求只属于该字符串的本质不同的非空子串的个数

题解

难度一般，建一个广义 $SAM$ 在 $Parent$ 树上对 $endpos$ 全部属于同一个字符串的统计即可

关键是下面的错误和解决方法

大部分直接按照 $maxlen$ 拓扑序会 $WA$，是因为如果字符串具有相同前缀则在广义 $SAM$ 中会出现 $maxlen(parent(A))=maxlen(A)$

主要是因为大部分广义 $SAM$ 的写法每次都必须新建一个 $np$ 节点，但实际上这个 $np$ 节点所表示的原串的前缀有可能在 $SAM$ 上出现了，但由于 $Parent$ 树的性质两者间有边相连，导致了 $maxlen$ 非严格单调递增的父子关系，可以通过 $\{ab,abc\}$ 体会一下 所以当 $maxlen$ 相同时，后加入的节点要靠后

但是按照我这种写法又 $WA$ 第 $2$ 个点，是由于新建的 $nq$ 节点应该继承 $np$ 节点的某一个 $endpos$ 而不是 $q$ 节点的 $endpos$

原因是我们会认为在某次加入操作时 $nq$ 的加入顺序晚于 $np$，导致 $np$ 最后不能及时更新 $nq$，那么一开始我们就应该将更晚的 $np$ 的某一个 $endpos$ 赋值给 $nq$

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cctype>
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;
}