BZOJ2780:[Spoj]8093 Sevenk Love Oimaster 后缀自动机+离线+dfs序+树状数组

思路:

首先建立多串后缀自动机(别问我怎么建的)

然后对于每个询问串在自动机上走,记录下走到的节点.那么在几个串中出现等价于逆序后缀树的子树中有几个原串的后缀.

转化为dfs序之后,这等价于每次询问一段区间有几种不同的数.

经典模型,离线+树状数组水.

(我TTMD坑了QoQ)

#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
#include<map>
using namespace std;
   
int n,m;
struct Graph{
    int head[200010],next[200010],end[200010],ind;
    inline void addedge(int a,int b){static int q=1;end[q]=b,next[q]=head[a],head[a]=q++;}
}w,g;
   
int len[200010],deg[200010],pa[200010],cnt,root,last;
map<int,int>tranc[200010];
int newnode(int l){
    len[++cnt]=l;return cnt;
}
   
char s[360010];
   
int in[200010],out[200010],seq[200010],tclock;
inline void dfs(int x){
    in[x]=++tclock;seq[tclock]=x;
    for(int j=g.head[x];j;j=g.next[j])dfs(g.end[j]);
    out[x]=tclock;
}
   
int pre[10010];
struct Ask{
    int lab,l,r;
    Ask(){}
    Ask(int _lab,int _l,int _r):lab(_lab),l(_l),r(_r){}
    bool operator<(const Ask&B)const{return r<B.r;}
}S[60010];
   
int A[200010];
inline void mdf(int x,int add){
    for(;x<=cnt;x+=x&-x)A[x]+=add;
}
inline int ask(int x){
    int r=0;for(;x;x-=x&-x)r+=A[x];return r;
}
   
int lastins[10010];
int ans[60010];
   
void get(int x){for(int j=w.head[x];j;j=w.next[j])printf("%d ",w.end[j]);puts("");}
   
int main(){
    scanf("%d%d",&n,&m);
    register int i,j,k;int l,y,p,np,q,nq,rep,tmp;
    for(root=newnode(0),i=1;i<=n;++i){
        scanf("%s",s);l=strlen(s);
        for(last=root,j=0;j<l;++j){
            if((p=tranc[last][y=s[j]])!=0){
                if(len[p]==len[last]+1)last=p;
                else{
                    rep=newnode(len[last]+1);pa[rep]=pa[p],pa[p]=rep;
                    tranc[rep]=tranc[p];
                    for(tmp=last;tmp&&tranc[tmp][y]==p;tmp=pa[tmp])tranc[tmp][y]=rep;
                    last=rep;
                }
            }
            else{
                np=newnode(len[last]+1);
                for(p=last;p&&!tranc[p][y];p=pa[p])tranc[p][y]=np;
                if(!p)pa[np]=root;
                else{
                    q=tranc[p][y];
                    if(len[q]==len[p]+1)pa[np]=q;
                    else{
                        nq=newnode(len[p]+1),pa[nq]=pa[q],pa[np]=pa[q]=nq;
                        tranc[nq]=tranc[q];
                        for(;p&&tranc[p][y]==q;p=pa[p])tranc[p][y]=nq;
                    }
                }last=np;
            }
            w.addedge(last,i);
        }
    }
    for(i=1;i<=cnt;++i)if(pa[i])g.addedge(pa[i],i);
    dfs(1);
       
    bool find;
    for(i=1;i<=m;++i){
        scanf("%s",s);l=strlen(s);find=1;
        for(p=root,j=0;j<l;++j){
            y=s[j];if(!tranc[p][y]){find=0;break;}p=tranc[p][y];
        }
        if(find)S[i]=Ask(i,in[p],out[p]);else S[i]=Ask(i,-1,-1);
    }sort(S+1,S+m+1);
       
    int noww;k=1;while(k<=m&&S[k].l==-1)++k;
    for(i=1;i<=cnt;++i){
        for(j=w.head[seq[i]];j;j=w.next[j]){
            noww=w.end[j];
            mdf(i,1);if(lastins[noww])mdf(lastins[noww],-1);lastins[noww]=i;
        }
        for(;S[k].r==i;++k)ans[S[k].lab]=ask(S[k].r)-ask(S[k].l-1);
    }
       
    for(i=1;i<=m;++i)printf("%d\n",ans[i]);
    return 0;
}