题意：有n种病毒序列（字符串），一个模式串，问这个字符串包括几种病毒。

包括相反的病毒也算。字符串中[qx]表示有q个x字符。具体见案列。

0 < q <= 5,000,000尽然不会超，无解

3

2

AB

DCB

DACB

3

ABC

CDE

GHI

ABCCDEFIHG

4

ABB

ACDEE

BBB

FEEE

A[2B]CD[4E]F

0

3

2

Hint

In the second case in the sample input, the reverse of the program is ‘GHIFEDCCBA’, and ‘GHI’ is a substring of the reverse, so the program is infected

by virus ‘GHI’.

#include<stdio.h>

#include<string.h>

#include<stdlib.h>

#include<string>

#include<queue>

#include<math.h>

#include<algorithm>

#include<iostream>

using namespace std;

const int kind = 26;

const int maxn = 250*1000; //注意RE,单词长度*单词个数

const int M = 5100000;

struct node

{

    node *fail;

    node *next[kind];

    int count;

    node()

    {

        fail = NULL;

        count = 0;

        memset(next,0,sizeof(next));

    }

}*q[maxn];

char keyword[1010],str[M],str1[M];

int head,tail;

void insert(char *str,node *root)

{

    node *p=root;

    int i=0,index;

    while(str[i])

    {

        index = str[i] - 'A';

        if(p->next[index]==NULL)

            p->next[index] = new node();

        p = p->next[index];

        i++;

    }

    p->count++;

}

void build_ac(node *root)

{

    int i;

    root->fail=NULL;

    q[head++]=root;

    while(head!=tail)

    {

        node *temp = q[tail++];

        node *p=NULL;

        for(i=0;i<26;i++)

        {

            if(temp->next[i]!=NULL)

            {

                if(temp==root)

                    temp->next[i]->fail=root;//失败指针指向root

                else

                {

                    p = temp->fail;

                    while(p!=NULL)

                    {

                        if(p->next[i]!=NULL)

                        {

                            temp->next[i]->fail=p->next[i];

                            break;

                        }

                        p=p->fail;

                    }

                    if(p==NULL)

                        temp->next[i]->fail=root;

                }

                q[head++]=temp->next[i];

            }

        }

    }

}

int query(node *root)

{

    int i=0,cnt=0,index,len=strlen(str);

    node *p=root;

    while(str[i])

    {

        index = str[i]-'A';

        while(p->next[index]==NULL&&p!=root)

            p = p->fail;

        p=p->next[index];

        p=(p==NULL)?root:p;

        node *temp = p;

        while(temp!=root&&temp->count!=-1)//沿失配边走，走过的不走

		{

            cnt+=temp->count;

            temp->count=-1;

            temp=temp->fail;

        }

        i++;

    }

    return cnt;

}

int value(int p,int q)

{

    int i,ans=0,w=1;

    for (i=q;i>=p;i--)

    {

        ans+=(str1[i]-'0')*w;

        w*=10;

    }  

    return ans;

}

int main()

{

    int n,t;

    scanf("%d",&t);

    while(t--)

    {

        head=tail=0;

        node *root = new node();

        scanf("%d",&n);

        while(n--)

        {

            scanf("%s",keyword);

            insert(keyword,root);

        }

        build_ac(root);

        scanf("%s",str1);

		int l=strlen(str1),i,j,k;  

        j=0;

        for (i=0;i<l;)

        {

            if (str1[i]!='[') str[j++]=str1[i++];

            else

            {

                /*for (k=i+1;str1[k]!=']';k++);

				int v=0,w=1;

				for (int l=k-2;l>=i+1;l--)

				{

					v+=(str1[l]-'0')*w;

					w*=10;

				}  */

				int v=0;

				i++;

				while(str1[i]>='0'&&str1[i]<='9')

				{

					v=v*10+str1[i]-'0';

					i++;

				}

                for (int k1=1;k1<=v;k1++) str[j++]=str1[i];  

                i+=2;

            }

        }

        str[j]='\0';

        //printf("%s\n",str);  

        int h=query(root);

        char chh;  

        l=strlen(str);

        for (i=0;i<=(l-1)/2;i++)

        {

            chh=str[l-i-1];

            str[l-i-1]=str[i];

            str[i]=chh;

        }

        //printf("%s",str);

        h+=query(root);

        printf("%d\n",h);

    }

    return 0;

}

/*

3

2

AB

DCB

DACB

3

ABC

CDE

GHI

ABCCDEFIHG

4

ABB

ACDEE

BBB

FEEE

A[2B]CD[4E]F

*/