思路:

水题一道.

首先建立广义后缀树.

然后利用离线+树状数组搞出每一个节点在多少个串中.

然后如果这个节点在不少于\(k\)个串中,我们令这个结点的权值为这个节点父亲边的字符个数,否则为0.

随后我们预处理一下从根到每个节点路径上的权值和.

于是每个字符串的答案等于所有这个字符串的后缀节点的从根到该节点的权值和.

时间复杂度\(O(nlogn)\).

(貌似比一些后缀数组的神方法要好多了QoQ)

#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
using namespace std;
 
#define N 100010
 
int tranc[N<<1][26],len[N<<1],pa[N<<1],cnt,root,last;
inline int newnode(int l){len[++cnt]=l;return cnt;}
 
struct Graph{
    int head[N<<1],next[N<<1],end[N<<1],ind;
    inline void addedge(int a,int b){int q=++ind;end[q]=b,next[q]=head[a],head[a]=q;}
}w,g,sav;
 
char s[N];
 
int seq[N<<1],in[N<<1],out[N<<1],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;
}
 
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[N<<1];
 
int ans[N<<1],lastins[N];
 
int A[N<<1];
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 v[N<<1];
 
void dfs2(int x){
    v[x]+=v[pa[x]];
    for(int j=g.head[x];j;j=g.next[j])dfs2(g.end[j]);
}
 
void get(int x){
    for(int j=w.head[x];j;j=w.next[j])printf("%d ",w.end[j]);puts("");
}
 
int main(){
    int n,lim;scanf("%d%d",&n,&lim);
     
    register int i,j,k;int y;int p,np,q,nq,rep,tmp;
    for(root=newnode(0),i=1;i<=n;++i){
        scanf("%s",s);int l=strlen(s);
        for(last=root,j=l-1;j>=0;--j){
            if((p=tranc[last][y=s[j]-'a'])!=0){
                if(len[p]==len[last]+1)last=p;
                else{
                    rep=newnode(len[last]+1);pa[rep]=pa[p],pa[p]=rep;
                    memcpy(tranc[rep],tranc[p],sizeof 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;
                        memcpy(tranc[nq],tranc[q],sizeof tranc[q]);
                        for(;p&&tranc[p][y]==q;p=pa[p])tranc[p][y]=nq;
                    }
                }last=np;
            }
            w.addedge(last,i);
            sav.addedge(i,last);
        }
    }
     
    for(i=1;i<=cnt;++i)if(pa[i])g.addedge(pa[i],i);
    dfs(1);
     
    for(i=1;i<=cnt;++i)S[i]=Ask(i,in[i],out[i]);sort(S+1,S+cnt+1);
    for(k=i=1;i<=cnt;++i){
        for(j=w.head[seq[i]];j;j=w.next[j]){
            if(lastins[w.end[j]])mdf(lastins[w.end[j]],-1);mdf(lastins[w.end[j]]=i,1);
        }
        for(;S[k].r==i;++k)ans[S[k].lab]=ask(S[k].r)-ask(S[k].l-1);
    }
     
    for(i=1;i<=cnt;++i)v[i]=ans[i]>=lim?len[i]-len[pa[i]]:0;
     
    dfs2(1);
     
    long long nowans;
    for(i=1;i<=n;++i){
        if(i>1)putchar(' ');
        for(nowans=0,j=sav.head[i];j;j=sav.next[j])nowans+=v[sav.end[j]];
        printf("%lld",nowans);
    }
     
    return 0;
}

思路:

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

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

转化为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;
}