国产探花免费观看_亚洲丰满少妇自慰呻吟_97日韩有码在线_资源在线日韩欧美_一区二区精品毛片,辰东完美世界有声小说,欢乐颂第一季,yy玄幻小说排行榜完本

首頁 > 學院 > 開發設計 > 正文

HDU-2222 Keywords Search

2019-11-14 09:48:29
字體:
來源:轉載
供稿:網友

題目鏈接: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; }
發表評論 共有條評論
用戶名: 密碼:
驗證碼: 匿名發表
主站蜘蛛池模板: 班戈县| 襄垣县| 齐齐哈尔市| 资中县| 锦屏县| 福泉市| 合水县| 铁岭县| 青龙| 禹州市| 望都县| 曲周县| 吉安县| 郎溪县| 新安县| 蛟河市| 山西省| 固始县| 泾川县| 浮山县| 太湖县| 洛扎县| 呼玛县| 邵阳县| 若尔盖县| 巴彦淖尔市| 康保县| 鲜城| 德惠市| 航空| 化州市| 隆回县| 大同市| 大关县| 高唐县| 嘉义县| 宿州市| 新巴尔虎左旗| 当涂县| 上饶市| 山西省|