BZOJ 3926 广义后缀自动机

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

添加新评论

bst g22 jinniu lilai opebet orange88 vinbet xbet yuebo zunlong shijiebei bet007 hg0088 ju111 letiantang m88 mayaba qg777 qianyiguoji sbf777 tengbohui tlc ule weilianxier waiweitouzhu xingfayule xinhaotiandi yinheyule youfayule zhongying 2018shijiebei w88 18luck 188bet beplay manbet 12bet 95zz shenbo weide1946 ca88 88bifa aomenxinpujing betway bodog bt365 bwin tongbao vwin weinisiren 88jt fenghuangyule hongyunguoji 918botiantang huanyayule jianada28 jixiangfang libo long8 hongzuyishi zuqiutouzhu