SP8093 JZPGYZ - Sevenk Love Oimaster

FxorG · 2021-07-08 11:00:39 · 个人记录

\text{Solution}

最开始想了个建广义SAM，然后用bitset维护树上信息，就取个并集，对于一个询问串暴力跳son。后来发现复杂度也许挺难的（有这样过的大佬能发下代码吗？）

但实际上可以离线下来，我们发现，跳到最后一个的时候，我们要取这时的bitset。因为parent树的父亲是子节点的后缀，所以父亲节点所匹配到的儿子一定能匹配。这时候可以用dfs序搞到子树区间，转化为区间数颜色问题。

\text{Code}

#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <vector>

#define N (int)(5e5+5)

using namespace std; 

struct edge {
    int nex,to;
}e[N];

struct ques {
    int l,r,id;
    bool operator < (const ques &x) const {
        return r==x.r?l<x.l:r<x.r;
    }
}q[N];

vector<int>col[N];
char s[N];
int head[N],cnt;
int fa[N],id[N],ans[N],rk[N],sz[N],son[26][N],len[N],pre_c[N];
int n,m,tot=1,las=1,slen;

int ins(int c) {
    if(son[c][las]) {
        int pre=las,y=son[c][las]; 
        if(len[pre]+1==len[y]) return y;
        int x=++tot; len[x]=len[pre]+1;
        fa[x]=fa[y]; fa[y]=x;
        for(int i=0;i<26;i++) son[i][x]=son[i][y];
        for(;pre&&son[c][pre]==y;pre=fa[pre]) son[c][pre]=x;
        return x;
    }
    int x=++tot,pre=las; len[x]=len[pre]+1; 
    for(;pre&&!son[c][pre];pre=fa[pre]) son[c][pre]=x;
    int y=son[c][pre];
    if(!pre) fa[x]=1;
    else if(len[pre]+1==len[y]) fa[x]=y;
    else {
        int p=++tot; len[p]=len[pre]+1;
        fa[p]=fa[y]; fa[x]=fa[y]=p;
        for(int i=0;i<26;i++) son[i][p]=son[i][y];
        for(;pre&&son[c][pre]==y;pre=fa[pre]) son[c][pre]=p;
    }
    return x;
} 

void add_edge(int x,int y) {
    e[++cnt].nex=head[x]; e[cnt].to=y; head[x]=cnt;
}

int dtot=0;
void dfs1(int x) {
    id[x]=++dtot; rk[dtot]=x; sz[x]=1;
    for(int i=head[x];i;i=e[i].nex) {
        int y=e[i].to;
        dfs1(y); sz[x]+=sz[y];
    }
}

int sum[N];
int lowbit(int x) {
    return x&(-x);
}

void add(int x,int v) {
    while(x<N) sum[x]+=v,x+=lowbit(x);
}

int qry(int x) {
    int res=0;
    while(x) res+=sum[x],x-=lowbit(x);
    return res;
}

int main() {
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) {
        scanf("%s",s+1); slen=strlen(s+1); las=1;
        for(int j=1;j<=slen;j++) {
            las=ins(s[j]-'a');
            col[las].push_back(i); 
        //  cout<<las<<endl;
        }
    }
    for(int i=2;i<=tot;i++) add_edge(fa[i],i);
    dfs1(1); int qcnt=0;
    for(int i=1;i<=m;i++) {
        scanf("%s",s+1); slen=strlen(s+1); 
        int p=1;
        for(int j=1;j<=slen&&p;j++) p=son[s[j]-'a'][p];
        if(p) {
            q[++qcnt].l=id[p],q[qcnt].r=id[p]+sz[p]-1,q[qcnt].id=i;
    //      cout<<id[p]<<":"<<endl;
        }
    }
    sort(q+1,q+1+qcnt);
    int nr=1;// puts("qwq");
    for(int i=1;i<=qcnt;i++) {
    //  cout<<q[i].l<<" "<<q[i].r<<endl;
        while(nr<=q[i].r) {
            for(int j=0;j<col[rk[nr]].size();j++) {
                if(pre_c[col[rk[nr]][j]]) add(pre_c[col[rk[nr]][j]],-1);
                add(nr,1); pre_c[col[rk[nr]][j]]=nr;
            }
        //  cout<<nr<<endl;
            ++nr;
        }
        ans[q[i].id]=qry(q[i].r)-qry(q[i].l-1);
    }
    for(int i=1;i<=m;i++) printf("%d\n",ans[i]);
    return 0;
}