HDU 2222 Keywords Search AC自动机模板

题目链接:

hdu2222

代码:

#include<iostream>#include<cstdio>#include<string>#include<cstring>#include<queue>using namespace std;struct node{int sum;node* fail;node* next[26];node(){sum=0;fail=NULL;for(int i=0; i<26; i++)next[i]=NULL;}};node* AC_insert(node* root,string word){int len=word.size();node* p=root;for(int i=0; i<len; i++){if(!p->next[word[i]-'a'])p->next[word[i]-'a']=new node();p=p->next[word[i]-'a'];}p->sum++;return root;}void build_fail(node* root){queue<node*>q;node *p,*temp;q.push(root);while(!q.empty()){p=q.front();q.pop();for(int i=0; i<26; i++)if(p->next[i]){if(p==root)p->next[i]->fail=root;else{temp=p->fail;while(temp){if(temp->next[i]){p->next[i]->fail=temp->next[i];break;}temp=temp->fail;}if(!temp)p->next[i]->fail=root;}q.push(p->next[i]);}}}int match(node* root,string s){int len=s.size(),ans=0;node *p=root,*temp;for(int i=0;i<len;i++){while(p!=root&&!p->next[s[i]-'a'])p=p->fail;p=p->next[s[i]-'a'];if(p==NULL)p=root;temp=p;while(temp!=root&&temp->sum!=-1){ans+=temp->sum;temp->sum=-1;temp=temp->fail;}}return ans;}int main(){// freopen("in.txt","r",stdin);int T,n;node* root;string word,Target_str;scanf("%d",&T);while(T–){root=new node();scanf("%d",&n);for(int i=0; i<n; i++){cin>>word;root=AC_insert(root,word);}build_fail(root);cin>>Target_str;printf("%d\n",match(root,Target_str));}return 0;}

,世上最累人的事,莫过於虚伪的过日子

HDU 2222 Keywords Search AC自动机模板

相关文章:

你感兴趣的文章:

标签云: