题意:给出多组模式串,再给出一个母串,问多少模式串是母串的字串。
裸AC自动机题,来试模板的。
#include <iostream> #include<cstring> #include<algorithm> #include<cstdio> #include<queue> using namespace std; char key[55],des[1000005]; const int MAX_NODE = 1000005; const int SIGMA_SIZE = 26; int size; struct node { node* fail; node* next[SIGMA_SIZE]; int count; void init() { fail=NULL; count=0; memset(next, 0, sizeof(next)); } }; class AC_Automation { public: void init(); void insert(char* str); void getFail(); int find(char* str); private: node* new_node(); node Heap[MAX_NODE]; node* root; int size; }; node* AC_Automation::new_node() { Heap[size].init(); return &Heap[size++]; } void AC_Automation::init() { size=0; root=new_node(); } void AC_Automation::insert(char* str) { node* p=root; for( ; *str; ++str) { int ch=*str-'a'; if(p->next[ch]==NULL) p->next[ch] = new_node(); p=p->next[ch]; } ++p->count; } void AC_Automation::getFail() { queue<node*>Q; Q.push(root); while(!Q.empty()) { node* tmp=Q.front(); Q.pop(); node* p; for(int i=0; i<SIGMA_SIZE; ++i) { node*& now=tmp->next[i]; if(now != NULL) { Q.push(now); if(tmp==root) { now->fail=root; continue; } p = tmp->fail; while(p != NULL) { if(p->next[i] != NULL) { now->fail = p->next[i]; break; } p=p->fail; } if(p==NULL) now->fail=root; } else { if(tmp==root) now=root; else now=tmp->fail->next[i]; } } } } int AC_Automation::find(char* str) { node* p=root; int cnt=0; for( ; *str; ++str) { char ch=*str-'a'; p = p->next[ch]; if(p==NULL) p=root; node* tmp=p; while(tmp!=root && tmp->count!=-1) { cnt += tmp->count; tmp->count=-1; tmp=tmp->fail; } } return cnt; } AC_Automation ac; int main() { int n,t; scanf("%d",&t); while(t--) { scanf("%d",&n); ac.init(); for(int i=0; i<n; i++) scanf("%s",key),ac.insert(key); ac.getFail(); scanf("%s",des); printf("%d\n",ac.find(des)); } return 0; }