| syhd142 |
|
|||
|
日歷
統計
導航常用鏈接留言簿(2)隨筆檔案(23)文章分類(270)
文章檔案(122)我的豆瓣搜索最新評論
|
模板題 #include <stdio.h>
#include <string.h> #include <math.h> #include <queue> #define KIND 26 #define N 1005 #define M 2000005 struct node { node *fail; node *next[KIND]; int id; node () { fail = NULL; id = 0; memset(next, 0, sizeof(next)); } }; char ch[M], key[N][55]; int count[N]; void insert(node *&root, char *ch, int num) { node *p = root; int i = 0, t; while(ch[i]) { t = ch[i] - 'A'; if(!p->next[t]) p->next[t] = new node(); p = p->next[t]; i++; } p->id = num; } void AC(node *&root) { std::queue<node *> q; q.push(root); while(!q.empty()) { node *p = NULL; node *t = q.front(); q.pop(); for(int i = 0; i < KIND; i++) { if(t->next[i]) { p = t->fail; while(p) { if(p->next[i]) { t->next[i]->fail = p->next[i]; break; } p = p->fail; } if(!p) t->next[i]->fail = root; q.push(t->next[i]); } } } } void query(node *&root, char *ch) { int i = 0, t; node *p = root, *tmp; while(ch[i]) { if(ch[i] > 'Z' || ch[i] < 'A') { p = root; i++; continue; } t = ch[i] - 'A'; while(!p->next[t] && p != root) p = p->fail; p = p->next[t]; if(!p) p = root; tmp = p; while(tmp != root) { count[tmp->id]++; tmp = tmp->fail; } i++; } } int main() { int n; while(~scanf("%d", &n)) { node *root = new node(); memset(count, 0, sizeof(count)); for(int i = 1; i <= n; i++) { scanf("%s", key[i]); insert(root, key[i], i); } AC(root); scanf("%s", ch); query(root, ch); for(int i = 1; i <= n; i++) { if(count[i]) { printf("%s: %d\n", key[i], count[i]); } } } return 0; }
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
![]() |
|
| Copyright © Fucker | Powered by: 博客園 模板提供:滬江博客 |