首页 > 代码库 > HDU 3695 Computer Virus on Planet Pandora (AC自动机)
HDU 3695 Computer Virus on Planet Pandora (AC自动机)
题意:有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 2HintIn 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 */
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。