HDU 3695 Computer Virus on Planet Pandora（10年福州 AC自动机）
转载请注明出处，谢谢http://blog.csdn.net/acm_cxlove/article/details/7854526 by---cxlove
题目：一些字典，然后给出一个主串，问正向和反向的一起出现了多少个模式串
http://acm.hdu.edu.cn/showproblem.php?pid=3695
建好AC自动机后，正向和反向扫描一遍就行了。
就是解析原串坑。。无聊
而且数据很大，500W的串
#include<iostream>#include<cstdio>#include<map>#include<cstring>#include<cmath>#include<vector>#include<algorithm>#include<set>#include<string>#include<queue>#define inf 1<<28#define M 6000005#define N 1000005#define Min(a,b) ((a)<(b)?(a):(b))#define Max(a,b) ((a)>(b)?(a):(b))#define pb(a) push_back(a)#define mem(a,b) memset(a,b,sizeof(a))#define LL long long#define MOD 1000000007using namespace std;class Trie{public:Trie *next[26],*fail;int word;Trie(){word=0;mem(next,NULL);fail=NULL;}};Trie *que[M];int tot;Trie *NewNode(){Trie *tmp=new Trie;mem(tmp->next,NULL);tmp->word=0;return tmp;}void Insert(Trie *root,char *s,int len){Trie *t=root;for(int i=0;i<len;i++){if(t->next[s[i]-'A']==NULL)t->next[s[i]-'A']=new Trie();t=t->next[s[i]-'A'];}t->word++;}void Bulid_fail(Trie *root){int head=0,tail=0;que[tail++]=root;root->fail=NULL;while(head<tail){Trie *temp=que[head++],*p;for(int i=0;i<26;i++){ if(temp->next[i]==NULL) continue; if(temp==root) temp->next[i]->fail=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; } que[tail++]=temp->next[i]; } }}int AC(Trie *root,char *s,int len){ Trie *p=root; int cnt=0; for(int i=0;i<len;i++){ while(p->next[s[i]-'A']==NULL&&p!=root) p=p->fail; p=p->next[s[i]-'A']; p=(p==NULL)?root:p; Trie *temp=p; while(temp!=root){ if(temp->word>0){ cnt+=temp->word; temp->word=0; } else break; temp=temp->fail; } } return cnt;}char str1[M],str2[M],str3[M];void change(){ int len1=strlen(str1),num,i,j; int len2=0; for(i=0;i<len1;i++){ if(str1[i]>='A'&&str1[i]<='Z'){ str2[len2++]=str1[i]; continue; } if(str1[i]=='['){ i++; num=0; for(;str1[i]>='0'&&str1[i]<='9';i++) num=num*10+str1[i]-'0'; int ll=len2; for(j=ll;j<ll+num;j++){ str2[j]=str1[i]; len2++; } i+=1; } } str2[len2]='\0';str3[len2]='\0'; for(i=0;i<len2;i++) str3[i]=str2[len2-i-1]; }int main(){int t,n;scanf("%d",&t);while(t--){tot=0;Trie *root=new Trie();scanf("%d",&n);for(int i=0;i<n;i++){char str[1005];scanf("%s",str);Insert(root,str,strlen(str));}Bulid_fail(root);scanf("%s",str1);change();printf("%d\n",AC(root,str2,strlen(str2))+AC(root,str3,strlen(str3)));}return 0;}