题意：有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

 

Sample Output

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
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             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
             
              =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;}/*32ABDCBDACB3ABCCDEGHIABCCDEFIHG4ABBACDEEBBBFEEEA[2B]CD[4E]F*/