欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

AC自动机入门详解+例题 hdu2222

程序员文章站 2022-06-04 12:30:36
...

首先简要介绍一下AC自动机:Aho-Corasick automation,该算法在1975年产生于贝尔实验室,是著名的多模匹配算法之一。一个常见的例子就是给出n个单词,再给出一段包含m个字符的文章,让你找出有多少个单词在文章里出现过。要搞懂AC自动机,先得有字典树Trie和KMP模式匹配算法的基础知识。KMP算法是单模式串的字符匹配算法,AC自动机是多模式串的字符匹配算法。

因为AC自动机算法是建立在字典树的基础上,如果不太了解字典树,就先自行普及一下字典树,这里和KMP算法相似的地方是因为这儿每个字典树节点中都要包含一个fail域,表示当前这个节点失配后要从fail节点开始匹配。
下面以she he say shr her为单词以yasherhs为文本串来匹配。可以画出下图
AC自动机入门详解+例题 hdu2222
图中虚线部分表示每个节点的fail指针的指向。
下边具体看一下fail指针的求法
fail指针用BFS来求得,对于直接与根节点相连的节点来说,如果这些节点失配,他们的Fail指针直接指向root即可,其他节点其Fail指针求法如下:
假设当前节点为father,其孩子节点记为child。求child的Fail指针时,首先我们要找到其father的Fail指针所指向的节点,假如是t的话,我们就要看t的孩子中有没有和child节点所表示的字母相同的节点,如果有的话,这个节点就是child的fail指针,如果发现没有,则需要找father->fail->fail这个节点,然后重复上面过程,如果一直找都找不到,则child的fail指针就要指向root。
下边我们来看一下fail指针的具体用法,在匹配过程中有两种情况;
(1)当前字符匹配,表示从当前节点沿着树边有一条路径可以到达目标字符,如果当前匹配的字符是一个单词的结尾,我们可以沿着当前字符的fail指针,一直遍历到根,如果这些节点末尾有标记(此处标记代表,节点是一个单词末尾的标记),这些节点全都是可以匹配上的节点。我们统计完毕后,并将那些节点标记。此时只需沿该路径走向下一个节点继续匹配即可,目标字符串指针移向下个字符继续匹配;
(2)当前字符不匹配,则去当前节点失败指针所指向的字符继续匹配,匹配过程随着指针指向root结束。重复这2个过程中的任意一个,直到模式串走到结尾为止。
具体代码如下:

#include <bits/stdc++.h>
using namespace std;
struct Trie///节点类型
{
    Trie *fail;
    Trie *child[26];
    int is_str;
    Trie()///构造函数完成每个节点的初始化
    {
        is_str = 0;
        fail = NULL;
        for(int i=0;i<26;i++){
            child[i] = NULL;
        }
    }
};
Trie *root,*temp,*current;
char str[10000005],key[55];
int head,tail;
void _insert(char s[])///插入构造字典树
{
    current = root;
    for(int i=0;i<strlen(s);i++){
        int index = s[i]-'a';
        if(current->child[index] == NULL){
            temp = new Trie;
            current->child[index] = temp;
        }
        current = current->child[index];
    }
    current->is_str++;///标记一下根节点到这个节点表示一个单词
}
void Find_fail()///寻找失配指针
{
    queue<Trie*> Q;
    Q.push(root);
    Trie *p;
    while(!Q.empty()){
      temp = new Trie;
      temp = Q.front();Q.pop();
      for(int i=0;i<26;i++){
        if(temp->child[i]!=NULL){
            if(temp == root)
                temp->child[i]->fail = root;///根节点的孩子节点的失配指针指向根节点
            else{
                p = temp ->fail;///用一个指针p暂时保存当前节点的失配指针,首先等于他父亲节点的失配指针
                while(p){///从它父亲节点的失配指针开始找起,如果能找到一个和它相同的节点,这个节点就是当前节点的失配指针
                    if(p->child[i]!=NULL){
                        temp ->child[i] ->fail = p->child[i];
                        break;
                    }
                    p = p->fail;
                }
                if(p == NULL) temp->child[i]->fail = root;///如果找到根节点的失配指针还没有找到与它相同的节点,则这个节点的失配指针就是根节点
            }
            Q.push(temp->child[i]);
        }
      }
    }
}
int sum;
void AC_automation(char s[])
{
    current = root;
    int len = strlen(s);
    for(int i=0;i<len;i++){
        int index = s[i] - 'a';
        while(!current->child[index]&&current != root)///如果这个字符不存在,就找它的失配指针,直到找到失配指针为止
        current = current -> fail;
        current = current->child[index];
        if(!current) current = root;///看看失配指针的下一个字符是否存在,如若不存在就从失配指针开始找
        temp = current;
        while(temp != root)///一直从失配指针找下去,因为从根节点到每个适配指针,表示从根结点到这个节点表示字符串的后缀
        {
            if(temp->is_str>=0){///如果这个节点没有被找过就给它加上一次,因为不是单词,加上0,对结果没有影响
                sum += temp->is_str;
                temp->is_str = -1;///加上之后要标记一下
            }
            else  break;///否则就直接结束
            temp = temp->fail;
        }
    }
}
int main()
{
    int T;scanf("%d",&T);
    while(T--){
        int n;
        root = new Trie;
        scanf("%d",&n);
        for(int i=0;i<n;i++){
            scanf("%s",key);
            _insert(key);
        }
        Find_fail();
        sum = 0;
        scanf("%s",str);
        AC_automation(str);
        printf("%d\n",sum);
    }
    return 0;
}