更新时间:2022-08-12 16:17:12
思路:AC自动机模板题
分析:
1 只要把输入处理成一个字符串,然后对关键字建立trie树和求next
2 注意题目是说按照匹配到的顺序输出,所以这个地方注意一下。
代码:
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<queue> using namespace std; #define MAXN 600010 #define MAX 10010 #define N 15 int n , m , cnt; char text[MAXN]; struct Node{ Node *next; Node *child[N]; int number; }; Node node[MAXN]; 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]-'0'; 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]){ 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; } } } } bool find(){ int len = strlen(text); bool mark = false; Node *p = root; for(int i = 0 ; i < len ; i++){ int num = text[i]-'0'; while(p->child[num] == NULL && p != root) p = p->next; if(p->child[num]){ p = p->child[num]; Node *tmp = p; while(tmp){ if(tmp->number){ if(!mark){ printf("Found key:"); mark = true; } printf(" [Key No. %d]" , tmp->number); } tmp = tmp->next; } } } return mark; } int main(){ char str[MAXN]; while(scanf("%d%d%*c" , &n , &m) != EOF){ cnt = 0; root = newNode(); for(int i = 0 ; i < n ; i++){ gets(str); strcat(text , str); } int len = strlen(text); text[len] = '\0'; gets(str);/*读掉空行*/ for(int i = 0 ; i < m ; i++){ gets(str); for(int j = 1 ; j < n ; j++){ if(str[j] == ' ' && str[j-1] == ']'){ insert(str+j+1 , i+1); break; } } } getNext(); if(!find()) printf("No key can be found !"); printf("\n"); } return 0; }