题目链接：

题目大意：有多个文本，多个模式串。问每个模式串中，有多少个文本？（匹配可重复）

解题思路：

传统AC自动机是计算单个文本中，模式串出现次数。

这里比较特殊，每个文本需要单独计算，而且每个匹配在每个文本中只能计数1次。

比如add，d只能计数1次，而不是；两次。

所以循环逐个对文本Find。每个Find里，进行Hash，保证每个匹配串只计数1次。

由于匹配串可重复，在Insert之前，也需要离散化Hash一下，把重复的下标，指向最先插入的下标。

另外，本题会卡掉不正确AC自动机模板（ Find里要写成While(last!=root)而不是While(last->cnt)  ）

代码

#pragma comment(linker, "/STACK:1024000000,1024000000")#include "cstdio"#include "cstring"#include "string"#include "iostream"#include "queue"#include "vector"#include "algorithm"#include "map"using namespace std;#define maxn 26int ans[100005],mt[100005];string P[10005];struct Trie{    Trie *next[maxn],*fail;    int cnt;}*root;Trie *newnode(){    Trie *ret=new Trie;    memset(ret->next,0,sizeof(ret->next));    ret->fail=0;    ret->cnt=0;    return ret;}void init() {root=newnode();}void Insert(string str,int index){    Trie *pos=root;    for(int i=0;i
     
      next[c]) pos->next[c]=newnode();        pos=pos->next[c];    }    pos->cnt=index;}void getfail(){    queue
      
        Q;    for(int c=0;c
       
        next[c])        {            root->next[c]->fail=root;            Q.push(root->next[c]);        }        else root->next[c]=root;    }    while(!Q.empty())    {        Trie *x=Q.front();Q.pop();        for(int c=0;c
        
         next[c])            {                x->next[c]->fail=x->fail->next[c];                Q.push(x->next[c]);            }            else x->next[c]=x->fail->next[c];        }    }}void Find(string str){    map
         
           Hash;    Trie *pos=root,*last;    for(int i=0;i
          
           maxn) {pos=root;continue;} if(pos->next[c]) { pos=pos->next[c]; last=pos; while(last!=root) { if(!Hash.count(last->cnt)) { ans[last->cnt]++; Hash[last->cnt]++; } last=last->fail; } } }}int main(){ //freopen("in.txt","r",stdin); ios::sync_with_stdio(false); int n,m,s; string tmp; while(cin>>n) { map
           
             ms; memset(ans,0,sizeof(ans)); memset(mt,0,sizeof(mt)); init(); for(int i=1;i<=n;i++) cin>>P[i]; cin>>s; for(int i=1;i<=s;i++) { cin>>tmp; if(!ms.count(tmp)) { Insert(tmp,i); ms[tmp]=i; mt[i]=i; } else mt[i]=ms[tmp]; } getfail(); for(int i=1;i<=n;i++) Find(P[i]); for(int i=1;i<=s;i++) cout<
            
             <