HDU 3065 AC自動機
題意:給出大寫字母組成的模式串,再給出一個字串匹配,問每個模式串在母串中出現的次數,母串為可見字符ASCII。
注意字典樹開next的大小,沒看清題MLE好幾次。。
#include <iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<queue> using namespace std; const int kind = 28; int num[1005]; char str[2000002],key[1002][55]; struct node { node *fail; node *next[kind]; int id; int count;//記錄當前前綴是完整單詞出現的個數 node() { fail = NULL; count = 0; memset(next,NULL,sizeof(next)); id=-1; } }; void insert(char *str,node *root,int m) { 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++; p->id=m; } //尋找失敗指針 void build_ac_automation(node *root) { int i; queue<node *>Q; root->fail = NULL; Q.push(root); while(!Q.empty()) { node *temp = Q.front();//q[head++];//取隊首元素 Q.pop(); node *p = NULL; for(i=0; i<kind; i++) { if(temp->next[i]!=NULL)//尋找當前子樹的失敗指針 { 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.push(temp->next[i]); } } } } //詢問str中包含n個關鍵字中多少種即匹配 int query(node *root) { int i = 0,cnt = 0,index,len; len = strlen(str); node *p = root; while(str[i]) { if(str[i]>='A'&&str[i]<='Z') index = str[i]-'A'; else index=27; while(p->next[index]==NULL&&p!=root)//失配 p=p->fail; p=p->next[index]; if(p==NULL)//失配指針為根 p = root; node *temp = p; while(temp!=root&&temp->id!=-1)//尋找到當前位置為止是否出現病毒關鍵字 { //if(temp->count!=0) //cnt+=temp->count; num[temp->id]++; //temp->count=-1; temp=temp->fail; } i++; } return cnt; } int Delete(node *T) { if(T==NULL) return 0; for(int i=0; i<26; i++) if(T->next[i]!=NULL) Delete(T->next[i]); delete T; return 0; } int main() { int n; while(~scanf("%d\n",&n)) { node root; for(int i=0; i<n; i++) { gets(key[i]); insert(key[i],&root,i); } memset(num,0,sizeof(num)); build_ac_automation(&root); gets(str); query(&root); for(int i=0; i<n; i++) if(num[i]) printf("%s: %d\n",key[i],num[i]); Delete(&root); } return 0; }
最後更新:2017-04-03 16:48:51