题目链接：

题意：

给你n个字符串，m个询问，每次询问一个字符串

定义set(s)={(i,j)} 表示 s在第i个字符串中出现，且末尾位置为j。

对于一个询问，求set(Qi)=set(t) ，t串的数量。

题解：

如果是n=1,那么就是后缀自动机的一道裸题，答案就是Qi串匹配的最后一个节点x，ml[x]-ml[f[x]]。

现在是多个串，那么就建立一个广义后缀自动机。每次插入一个串后，将last=root，然后继续插下一个就行了。

最后匹配还是一样的操作。

1 #include
      
        2 #include
       
         3 #define F(i,a,b) for(int i=a;i<=b;++i) 4 #define mst(a,b) memset(a,b,sizeof(a)) 5 using namespace std; 6  7 const int N=1e5+7,tyn=26,M=N*2; 8 struct SAM{ 9     int tr[M][tyn],f[M],ml[M],ed,last,p,x,r,q;10     int cnt[M],b[M],d[M];11     inline int gid(char x){
    return x-'a';}12     inline void nc(int s,int &p){13         ml[p=++ed]=s,f[ed]=cnt[ed]=0,mst(tr[ed],0);14     }15     void clear(){ed=0,nc(0,last);}16     void add(int w){17         nc(ml[x=last]+1,p),last=p,cnt[p]=1;18         while(x&&!tr[x][w])tr[x][w]=p,x=f[x];19         if(!x)f[p]=1;20         else if(ml[x]+1==ml[q=tr[x][w]])f[p]=q;21         else{22             nc(ml[x]+1,r),f[r]=f[q],f[p]=f[q]=r;23             memcpy(tr[r],tr[q],sizeof(tr[r]));24             while(x&&tr[x][w]==q)tr[x][w]=r,x=f[x];25         }26     }27     void build(char *s){
    for(int i=1;s[i];i++)add(gid(s[i]));}28     29     int go(char *s,int x=1)//与s做匹配30     {31         int len=strlen(s+1);32         for(int i=1;i<=len;i++)33         {34             int w=gid(s[i]);35             if(tr[x][w])x=tr[x][w];36             else return 0;37         }38         return ml[x]-ml[f[x]];39     }40 }sam;41 42 char s[N];43 int t,n,m,cas;44 45 int main()46 {47     scanf("%d",&t);48     while(t--)49     {50         scanf("%d%d",&n,&m);51         sam.clear();52         F(i,1,n)53         {54             sam.last=1;55             scanf("%s",s+1);56             sam.build(s);57         }58         printf("Case #%d:\n",++cas);59         F(i,1,m)60         {61             scanf("%s",s+1);62             printf("%d\n",sam.go(s));63         }64     }65     return 0;66 }