【日常小测】最长公共前缀

题目大意

给定一棵以$1$号点为根、大小为$n$的有根树($n \le 10^5$),每一条边上有一个小写英文字母
给定$m$个询问,第$i$个询问包含一个长度为$t_i$的点集(元素可重,$\sum{t_i} \le 2 \cdot 10^5$),询问$\sum\limits_{a=1}^{t_i}{\sum\limits_{b=a+1}^{t_i}{lcp(a,b)}}$

定义$s_a$为从a出发走向根,将边上的字符按顺序写下来构成的字符串
定义$lcp(a,b)$为$s_a$与$s_b$的最长公共前缀

下面举一个栗子
若树长成这样:

那么$s_5=cb,s_4=cbb$
更进一步,若某次询问的点集为$\{4,5\}$那么答案为$2$

解题报告

看到这种树上的字符串,我能想到AC自动机,或者广义后缀自动机
想了想AC自动机做不了,那就广义后缀自动机来做咯!

考虑后缀自动机上的Fail树
一个点的祖先实际上是这个点代表的字符串的后缀
那么题目中的$lcp(a,b)$就变成了$lca(a,b)$
于是对于每一次询问,我们建一个虚树出来
然后在虚树上DFS一次,统计一下答案就好啦!

另外,这题用后缀数组也可以做!
听武爷讲一讲,大概就是先把Trie树建出来
同时记录下每一次倍增的$Rank$数组(波兰表……)
然后就正常倍增,写法已经和罗穗骞的后缀数组的实现很不同了

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;
 
const int N = 200009;
const int M = N << 1;
 
int n,m,E,head[N],nxt[M],to[M],col[M],pos[N],id[N];
 
inline int read() {
    char c=getchar(); int ret=0,f=1;
    while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
    while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
    return ret * f;
}
 
inline void Add_Edge(int u, int v, int c = 0) {
    to[++E] = v; nxt[E] = head[u]; head[u] = E; col[E] = c;
    to[++E] = u; nxt[E] = head[v]; head[v] = E; col[E] = c;
}   
 
class Suffix_Automaton{
	int cnt=1,ch[N][26],fail[N],vis[N],dep[N],sum[N];
	int tot,arr[N],que[N],len[N],fa[N][20],_hash[N];
	vector<int> G[N]; LL ans_tmp;
    public:
        inline int insert(int t, int cc) {
            if (ch[t][cc] && len[ch[t][cc]] == len[t] + 1) return ch[t][cc];
            int tail = ++cnt; len[tail] = len[t] + 1;
            while (!ch[t][cc] && t) ch[t][cc] = tail, t=fail[t];
            if (!t) fail[tail] = 1;
            else {
                if (len[ch[t][cc]] == len[t] + 1) fail[tail] = ch[t][cc];
                else {
                    int nw = ++cnt, w = ch[t][cc]; len[nw] = len[t]+1;
                    memcpy(ch[nw], ch[w], sizeof(ch[nw]));
                    fail[nw] = fail[w]; fail[w] = fail[tail] = nw;
                    for (;ch[t][cc]==w;t=fail[t]) ch[t][cc] = nw;
                }
            } return tail;
        }
        inline void Build_Fail_Tree() {
            memset(head,0,sizeof(head)); E = 0;
            for (int i=2;i<=cnt;i++) Add_Edge(fail[i], i);
            dfs(1, 1);
            for (int j=1;j<20;j++) {
                for (int i=1;i<=cnt;i++) {
                    fa[i][j] = fa[fa[i][j-1]][j-1];
                }
            }   
        }
        inline LL solve(int nn) {
            for (int i=1;i<=nn;i++) arr[i] = pos[read()];
            sort(arr+1, arr+1+nn, [](const int &a, const int &b) {return id[a] < id[b];});
            for (int i=1;i<=nn;i++) _hash[i] = arr[i];
            int mm = nn; nn = unique(arr+1, arr+1+nn) - arr - 1;
            for (int i=1;i<=nn;i++) sum[i] = 0;
            for (int i=1,j=1;i<=mm;i++) {
                while (arr[j] != _hash[i]) j++;
                sum[j]++;
            }
            que[tot=1] = 1; int MX = 1;
            for (int i=1,lca;i<=nn;i++) {
                vis[arr[i]] = sum[i];
                lca = LCA(que[tot], arr[i]);
                while (dep[que[tot]] > dep[lca]) {
                    if (dep[que[tot-1]] >= dep[lca]) G[que[tot-1]].push_back(que[tot]);
                    else G[lca].push_back(que[tot]);
                    --tot;
                }
                if (que[tot] != lca) que[++tot] = lca;
                if (arr[i] != que[tot]) que[++tot] = arr[i];
                MX = max(MX, tot);
            }
            while (tot > 1) G[que[tot-1]].push_back(que[tot]), --tot;
            ans_tmp = 0;
            Get_Ans(1);
            return ans_tmp;
        }
    private:
        void dfs(int w, int f) {
            static int id_count = 0;
            id[w] = ++id_count;
            fa[w][0] = f; dep[w] = dep[f] + 1;
            for (int i=head[w];i;i=nxt[i]) {
                if (to[i] != f) {
                    dfs(to[i], w);
                }
            }
        } 
        int Get_Ans(int w) {
            int ret = vis[w]; 
            if (w > 1) ans_tmp += vis[w] * (vis[w] - 1ll) / 2 * len[w]; 
            for (int i=G[w].size()-1,tmp;~i;i--) { 
                tmp = Get_Ans(G[w][i]);
                ans_tmp += (LL)tmp * ret * len[w];
                ret += tmp;
            }
            vis[w] = 0; 
            G[w].clear();
            return ret;
        }
        inline int LCA(int a, int b) {
            if (dep[a] < dep[b]) swap(a, b);
            for (int i=19;~i;i--) if (dep[fa[a][i]] >= dep[b]) a = fa[a][i];
            if (a == b) return a;
            for (int i=19;~i;i--) if (fa[a][i] != fa[b][i]) a = fa[a][i], b = fa[b][i];
            return fa[a][0];
        }   
}SAM;
 
void DFS(int w, int f, int t) {
    pos[w] = t;
    for (int i=head[w];i;i=nxt[i]) {
        if (to[i] != f) {
            int nt = SAM.insert(t, col[i]);
            DFS(to[i], w, nt);
        }
    }
}
 
int main() {
    n = read(); char pat[10];
    for (int i=1,u,v;i<n;i++) {
        u = read(); v = read();
        scanf("%s",pat+1);
        Add_Edge(u, v, pat[1] - 'a');
    }   
    DFS(1, 1, 1);
    SAM.Build_Fail_Tree();
    for (int i=read();i;i--) 
        printf("%lld\n",SAM.solve(read()));
    return 0;
}

12 thoughts to “【日常小测】最长公共前缀”

  1. I’m not sure where you’re getting your info, but great topic.
    I needs to spend some time learning more or understanding
    more. Thanks for magnificent information I was looking for this info for my mission.

  2. I like the helpful information you provide in your articles.
    I’ll bookmark your blog and check again here
    regularly. I am quite sure I will learn many new stuff right here!
    Good luck for the next!

  3. I was pretty pleased to uncover this site.
    I wanted to thank you for your time for this particularly wonderful read!!
    I definitely loved every bit of it and I have
    you saved as a favorite to see new things on your site.

  4. of course like your web site but you need to test the spelling on several of your posts.
    A number of them are rife with spelling issues and I in finding
    it very bothersome to inform the truth then again I will definitely come
    back again.

  5. Hi! Do you know if they make any plugins to protect against hackers?
    I’m kinda paranoid about losing everything I’ve worked hard on. Any suggestions?

  6. I am really loving the theme/design of your site. Do you ever run into any web browser compatibility issues?
    A number of my blog visitors have complained about my website not
    working correctly in Explorer but looks great in Firefox.
    Do you have any solutions to help fix this issue?

发表评论

电子邮件地址不会被公开。 必填项已用*标注