AC自动机模板题，稍微改一改就可以了

这个题目坑在是多组样例输入

#include
     
      using namespace std;const int maxn = 2000000+5;const int nsize = 26;struct node{    node *next[nsize];    node *fail;    int sum;};node *root;int cnt[1005];//构造字典树void Insert(char *s, int id){    node *newnode,*p;    p = root;    for(int i = 0; s[i]; i++)    {        int x = s[i] - 'A';        if(p->next[x] == NULL)        {            newnode=(struct node *)malloc(sizeof(struct node));            for(int j=0; j
      
       next[j] = 0;            newnode->sum = 0;            newnode->fail = 0;            p->next[x]=newnode;        }        p = p->next[x];    }    p->sum = id;}//构造失败指针void build_fail(){    queue
       
         Q;    Q.push(root);    while (!Q.empty())    {        node *p = Q.front();        Q.pop();        for(int i = 0; i < nsize; i++)        {            if (p->next[i])            {                if (p == root)                    p->next[i]->fail = p;                else                {                    node *tmp = p->fail;                    while (tmp)                    {                        if (tmp->next[i])                        {                            p->next[i]->fail = tmp->next[i];                            break;                        }                        else tmp = tmp->fail;                    }                    if (!tmp) p->next[i]->fail = root;                }                Q.push(p->next[i]);            }        }    }    return ;}//匹配void ac_automation(char *ch){    node *p = root;    int len = strlen(ch);    for(int i = 0; i < len; i++)    {        if(ch[i] > 'Z' || ch[i] < 'A')        {            p = root;            continue;        }        int x = ch[i] - 'A';        while(!p->next[x] && p != root)        {            p = p->fail;            if(p->sum > 0)            {                cnt[p->sum]++;            }        }        p = p->next[x];        if(!p) p = root;        node *temp = p;        while(temp != root)        {            if(temp->sum > 0)            {                cnt[temp->sum]++;            }            else break;            temp = temp->fail;        }    }}char sbs[1005][55],str[maxn];int main(){//    freopen("in.txt","r",stdin);    int N;    root=(struct node *)malloc(sizeof(struct node));    for(int j=0; j
        
         next[j] = 0;    root->fail = 0;    root->sum = 0;    while(~scanf("%d",&N))    {        memset(cnt, 0, sizeof(cnt));        for(int i = 1; i <= N; i++)        {            scanf("%s", sbs[i]);            Insert(sbs[i], i);        }        build_fail();        scanf("%s", str);        ac_automation(str);        for(int i = 1; i <= N; i++)        {            if(cnt[i] > 0)                printf("%s: %d\n", sbs[i], cnt[i]);        }    }    return 0;}