更新时间:2022-08-12 16:17:24
思路:AC自动机模板题
分析:
1 先对n个模板串构造trie树并且求出失配边
2 然后在文本串上面查找,找到是单词节点就把当前的单词个数加1,最后枚举输出即可。
代码:
#include<iostream> #include<cstdio> #include<cstring> #include<queue> #include<algorithm> using namespace std; #define MAXN 1000010 #define MAX 200 #define N 30 char text[MAXN]; char words[MAX][MAX]; int vis[MAX]; int n , cnt; struct Node{ Node *next; Node *child[N]; int number; }; Node node[MAX*MAX]; Node *root; queue<Node*>q; /*字典树的空间分配*/ Node* newNode(){ node[cnt].next = NULL; node[cnt].number = 0; for(int i = 0 ; i < N ; i++) node[cnt].child[i] = NULL; return &node[cnt++]; } /*单词插入字典树*/ void insert(char *str , int x){ int len = strlen(str); Node *p = root; for(int i = 0 ; i < len ; i++){ int num = str[i]-'a'; if(p->child[num] == NULL) p->child[num] = newNode(); p = p->child[num]; } p->number = x; } /*求失配边*/ void getNext(){ while(!q.empty()) q.pop(); q.push(root); root->next = NULL; while(!q.empty()){ Node *p = q.front(); q.pop(); for(int i = 0 ; i < N ; i++){ if(p->child[i] != NULL){ q.push(p->child[i]); Node *tmp = p->next; while(tmp){ if(tmp->child[i]){ p->child[i]->next = tmp->child[i]; break; } tmp = tmp->next; } if(tmp == NULL) p->child[i]->next = root; } } } } int find(){ int len = strlen(text); int Max = 0; Node *p = root; for(int i = 0 ; i < len ; i++){ int num = text[i]-'a'; while(p != root && p->child[num] == NULL) p = p->next; if(p->child[num] != NULL){ p = p->child[num]; Node *tmp = p; while(tmp != NULL){ if(tmp->number){ vis[tmp->number]++; Max = max(Max , vis[tmp->number]); } tmp = tmp->next; } } } return Max; } /*输出*/ void output(int x){ printf("%d\n" , x); for(int i = 1 ; i <= n ; i++){ if(vis[i] == x) printf("%s\n" , words[i]); } } int main(){ while(scanf("%d" , &n) && n){ cnt = 0; root = newNode(); memset(vis , 0 , sizeof(vis)); for(int i = 1 ; i <= n ; i++){ scanf("%s" , words[i]); insert(words[i], i); } scanf("%s" , text); getNext(); output(find()); } return 0; }