題目鏈接：http://acm.hdu.edu.cn/showPRoblem.php?pid=2222 思路： 題目大意是，提供n個單詞以及一段話，問在這段話中所給單詞在文章中出現的個數。使用AC自動機算法來解題。
AC代碼：
#include<cstdio>#include<cstring>#include<queue>using namespace std;const int maxn=1000000;char str[maxn+10];struct node{ int count;//標識是否為葉子結點 struct node *next[26]; struct node *fail;//失敗指針 void init()//初始化函數 { for(int i=0;i<26;i++) next[i]=NULL; count=0; fail=NULL; } }*root;//構造樹TRIEvoid insert(){ node *p=root; int len=strlen(str); for(int i=0;i<len;i++) { int pos=str[i]-'a'; if(p->next[pos]==NULL) { p->next[pos]=new node; p->next[pos]->init(); p=p->next[pos]; } else p=p->next[pos]; } p->count++;//標識為單詞尾部 } //構造失敗指針 void getfail() { node *p=root,*son,*temp; queue<struct node *>que; que.push(p);//root入隊 while(!que.empty()) { temp=que.front(); que.pop(); for(int i=0;i<26;i++) { son=temp->next[i]; if(son!=NULL) { if(temp==root) son->fail=root; else { p=temp->fail; while(p) { if(p->next[i])//如果trie中有相同字母指向該字母的失敗指針 { son->fail=p->next[i]; break; } p=p->fail; } if(!p) son->fail=root; } que.push(son); } } } } //查找有多少個字符串在所給段落中出現 void query() { int ans=0; int len=strlen(str); node *p=root,*temp; for(int i=0;i<len;i++) { int pos=str[i]-'a'; while(!p->next[pos]&&p!=root) p=p->fail; p=p->next[pos]; if(!p) p=root; temp=p; while(temp!=root) { if(temp->count>=0)//找到改串單詞尾部 { ans+=temp->count; temp->count=-1;//標識該單詞找過，避免重復計算 } else break; temp=temp->fail; } } printf("%d/n",ans);//輸出個數 } int main() { int m,n; scanf("%d",&m); while(m--) { root=new node; root->init(); root->fail=NULL; scanf("%d",&n); getchar(); for(int i=0;i<n;i++) { scanf("%s",&str); insert();//構造TRIE } getfail();//建立失敗指針 scanf("%s",&str); query(); } return 0; }新聞熱點
疑難解答
