P4081 [USACO17DEC]Standing Out from the Herd

$ \color{#0066ff}{ 题目描述 }$

定义一个字符串的「独特值」为只属于该字符串的本质不同的非空子串的个数。如 "amy" 与 “tommy” 两个串，只属于 "amy" 的本质不同的子串为 "a" "am" "amy" 共 3 个。只属于 "tommy" 的本质不同的子串为 "t" "to" "tom" "tomm" "tommy" "o" "om" "omm" "ommy" "mm" "mmy" 共 11 个。 所以 "amy" 的「独特值」为 3 ，"tommy" 的「独特值」为 11 。

给定 N (\(N \leq 10^5\)) 个字符集为小写英文字母的字符串，所有字符串的长度和小于 \(10^5\)，求出每个字符串「独特值」。

\(\color{#0066ff}{输入格式}\)

第一行包含一个正整数n，字符串个数

接下来是n个字符串

\(\color{#0066ff}{输出格式}\)

每行一个答案

\(\color{#0066ff}{输入样例}\)

3
amy
tommy
bessie

\(\color{#0066ff}{输出样例}\)

3
11
19

\(\color{#0066ff}{数据范围与提示}\)

none

\(\color{#0066ff}{题解}\)

把所有字符串用不同的字符隔开拼起来，建立SAM

那么对于一个前缀，那些后缀会有贡献呢？

当且仅当这个后缀没有特殊字符！

那么有多少个后缀有特殊字符呢，就是最近的那个特殊字符的下标

比如abcde￥fghij#klnmo，每一个字符串维护一个f，代表以当前字符串中任意位置为结尾的所有后缀，有多少不合法的

比如klnmo这个字符串，不合法的后缀数量为abcde￥fghij#的长度12

如果一个点是后缀节点，那么它与它父亲的边上有一段是不合法的，就直接减去维护的f即可

否则直接有两个len之差的贡献

对于特殊字符，它不属于任意一个字符串，所以鸡排的时候顺带它向上的一条链都不合法

还有就是一个节点子树中有来自不同字符串的节点，这也是不合法的，统统\(\in -1\)就行

#include<bits/stdc++.h>
#define LL long long
LL in() {
    char ch; LL x = 0, f = 1;
    while(!isdigit(ch = getchar()))(ch == '-') && (f = -f);
    for(x = ch ^ 48; isdigit(ch = getchar()); x = (x << 1) + (x << 3) + (ch ^ 48));
    return x * f;
}
const int maxn = 4e5 + 100;
struct node {
    std::map<int, node*> ch;
    node *fa;
    int len, bel, siz;
    bool islast;
    node(int len = 0, int bel = 0, int siz = 0, bool islast = 0): len(len), bel(bel), siz(siz), islast(islast) {
        fa = NULL;
        ch.clear();
    }
}pool[maxn], *tail, *root, *lst;
LL ans[maxn];
int fuck[maxn];
node *id[maxn];
void extend(int c, int id) {
    node *o = new(tail++) node(lst->len + 1, id, 1), *v = lst;
    o->islast = true;
    for(; v && !v->ch.count(c); v = v->fa) v->ch[c] = o;
    if(!v) o->fa = root;
    else if(v->len + 1 == v->ch[c]->len) o->fa = v->ch[c];
    else {
        node *n = new(tail++) node(v->len + 1), *d = v->ch[c];
        n->ch = d->ch;
        n->fa = d->fa, d->fa = o->fa = n;
        for(; v && v->ch[c] == d; v = v->fa) v->ch[c] = n;
    }
    lst = o;
}
void getans() {
    int maxlen = 0, len = tail - pool;
    static int c[maxn];
    for(node *o = pool; o != tail; o++) maxlen = std::max(maxlen, o->len), c[o->len]++;
    for(int i = 1; i <= maxlen; i++) c[i] += c[i - 1];
    for(node *o = pool; o != tail; o++) id[--c[o->len]] = o;
    for(int i = len - 1; i; i--) {
        node *o = id[i];
        if(~o->bel) {
            if(o->islast) ans[o->bel] += o->len - o->fa->len - fuck[o->bel];
            else ans[o->bel] += o->len - o->fa->len;
        }
        else o->fa->bel = -1;
        if(!(~o->fa->bel)) continue;
        if(!o->fa->bel) o->fa->bel = o->bel;
        else if(o->fa->bel ^ o->bel) o->fa->bel = -1;
    }
}
void init() {
    tail = pool;
    root = lst = new(tail++) node();
}
char a[maxn];
int main() {
    int n = in();
    init();
    int cnt = 233;
    for(int i = 1; i <= n; i++) {
        if(i ^ 1) fuck[i] = fuck[i - 1] + strlen(a) + 1;
        scanf("%s", a);
        for(char *p = a; *p; p++) extend(*p, i);
        extend(++cnt, -1);
    }
    getans();
    for(int i = 1; i <= n; i++) printf("%lld\n", ans[i]);
    return 0;

}