BZOJ 3926 广义后缀自动机

给一棵树,点上有字母,问树上路径组成的本质不同的字符串有多少个。

$ n\le10^5,|\Sigma|\le10, |\text {leaves}| \le 20 $ .

Sol.

很久之前就会做……直到今天才来打……

打题半小时调题两小时……

注意到叶子特别少,以每个叶子为根的 trie 合并成一棵打 trie 后所有树上路径构成字符串都是大 trie 上一条从祖先到后代的路径。

对这棵打 trie 建广义后缀自动机(其实应该叫多串)。

注意到转移图的前驱结点就是 trie 上的父亲对应的结点,直接接上去就好。

不同串之间可能因为所在的 trie 不同却同时有相同的前驱,这会使得重复计算,因为前一棵 trie 的后面的串显然与当前 trie 的字符串不共享。我们显式的建出的转移图其实是有问题的,但因为我们求的这个自动机能识别的字符串个数,所以我们只关心 parent 树的结构,而这个显然是一直正确的,即便是隐式的。所以不必多做处理,每次都对当前 trie 结点都新开一个自动机结点即可。

Code

#include <bits/stdc++.h>
using namespace std;
template<class T> void read(T& x)
{
    char c = getchar(); T p = 1, n = 0;
    while(c < '0' || c > '9') {if(c == '-') p = -1; c = getchar();}
    while(c >= '0' && c <= '9'){n = n * 10 + c - '0'; c = getchar();}
    x = p * n;
}
template<class T,class U>void read(T&x,U&y){read(x),read(y);}
template<class T,class U,class V>void read(T&x,U&y,V&z){read(x),read(y),read(z);}
const int maxn = 1e5 + 10, sigma = 15;
struct E{int v, n;}e[maxn << 1];
int h[maxn], ec = 1;
inline void add_edge(int u, int v){e[ec] = (E){v, h[u]}; h[u] = ec++;}
struct N{int ch[sigma], f, len, cnt, n;} pool[maxn * sigma * sigma];
int h2[maxn], head = 1, pc = 2;
int add(int p, int c)
{
    int newnode = pc++;
    pool[newnode].n = h2[pool[newnode].len = pool[p].len + 1]; h2[pool[newnode].len] = newnode;
    pool[newnode].cnt = 0;
    for(; p && !pool[p].ch[c]; p = pool[p].f) pool[p].ch[c] = newnode;
    if(!p) pool[newnode].f = head;
    else if(pool[p].len + 1 == pool[pool[p].ch[c]].len) pool[newnode].f = pool[p].ch[c];
    else
    {
        int q = pool[p].ch[c], r = pc++;
        pool[r] = pool[q];
        pool[r].n = h2[pool[r].len = pool[p].len + 1]; h2[pool[r].len] = r;
        pool[q].f = pool[newnode].f = r;
        for(; p && pool[p].ch[c] == q; p = pool[p].f) pool[p].ch[c] = r;
    }
    return newnode;
}
int col[maxn];
void dfs(int s, int u, int f = 0)
{
    int t = add(s, col[u]);
    for(int i = h[u], v = e[i].v; i; i = e[i].n, v = e[i].v) if(v != f)
        dfs(t, v, u);
}
int deg[maxn];
int main()
{
    int n, c; read(n, c);
    for(int i = 1; i <= n; ++i) read(col[i]);
    for(int i = 1, u, v; i < n; ++i) read(u, v), add_edge(u, v), add_edge(v, u), ++deg[u], ++deg[v];
    for(int i = 1; i <= n; ++i) if(deg[i] == 1) dfs(head, i);
    long long ans = 0;
    for(int i = n; i; --i) for(int j = h2[i]; j; j = pool[j].n) 
        ans += pool[j].len - pool[pool[j].f].len;
    printf("%lld\n", ans);
    return 0;
}

标签: none

添加新评论