更新时间:2022-08-12 16:21:42
思路:AC自动机的模板题
分析:
AC自动机的三个步骤
1 利用文本串建立字典树
2 在字典树上面构造失配指针
3 在字典树上面匹配,求出个数。
代码:
#include<iostream> #include<cstdio> #include<cstring> #include<queue> #include<algorithm> using namespace std; #define MAXN 1000010 #define MAX 10010 #define N 26/*这个地方看是字母还是数字*/ struct Node{ Node *next;/*失配指针*/ Node *child[N];/*字典树最多的儿子节点的个数*/ int flag;/*标记是否是单词的最后一个节点*/ }; Node node[MAXN]; Node *root; queue<Node*>q; int cnt; int Case , n; char words[MAX][N*2]; char text[MAXN]; /*字典树静态分配空间*/ Node* newNode(){ node[cnt].next = NULL; node[cnt].flag = 0; for(int i = 0 ; i < N ; i++) node[cnt].child[i] = NULL; return &node[cnt++]; } /*字典树的插入*/ void insert(char *str){ Node *p = root; for(int i = 0 ; i < strlen(str) ; i++){ int num = str[i]-'a'; if(p->child[num] == NULL) p->child[num] = newNode(); p = p->child[num]; } p->flag++;/*记录该节点为结尾有几个单词*/ } /*求失配函数*/ void getNext(){ while(!q.empty()) q.pop(); q.push(root);/*首先把根节点入队列*/ root->next = NULL;/*根节点的nexe指向空(也可以自己)*/ 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;/*tmp是p的失配指针*/ /*沿着失配边走直到某一个节点也有child[i]儿子就把当前p->child[i]的失配指针赋为tmp->child[i]*/ 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;/*到root还没找到则失配指针为root*/ } } } } /*匹配的过程*/ int find(){ int sum = 0; int len = strlen(text); 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->flag){ sum += tmp->flag; tmp->flag = 0; } tmp = tmp->next;/*当找到一个模板串之和继续向失配边移动看有没有其它的串*/ } } } return sum; } int main(){ scanf("%d" , &Case); while(Case--){ scanf("%d" , &n); cnt = 0; root = newNode(); /*输入单词建立trie树*/ for(int i = 0 ; i < n ; i++){ scanf("%s" , words[i]); insert(words[i]); } scanf("%s" , text); getNext(); printf("%d\n" , find()); } return 0; }