【HDU 2222】Keywords Search（AC自动机模板）

深碍√TFBOYSˉ_ 2022-05-03 05:28 219阅读 0赞

题目：[点击打开题目链接][Link 1]

题意：多组测试样例，每组测试样例给你n个单词和一句话，问这n个单词有多少个可以在这句话中匹配的到，即n个单词中有哪些可以在这句话中找到。

思路：AC自动机的模板题

My DaiMa：

#include<iostream>
    #include<stdio.h>
    #include<string.h>
    #include<queue>
    #include<malloc.h>
    using namespace std;
    const int allson = 26;///此题中只用到了26个小写字母
    char patten[60];///模式串
    char text[1000005];///文本串
    int ans;
    struct TrieNode
    {
        struct TrieNode *son[allson];///儿子节点
        struct TrieNode *fail;///失败指针
        int num;///以该节点为结尾的字符串的单词数
    }*root;///根节点
    /*创建节点*/
    TrieNode * createNode()
    {
        TrieNode *p;
        p = (TrieNode*)malloc(sizeof(TrieNode));
        for(int i = 0; i < allson; i++) p->son[i] = NULL;
        p ->num = 0;
        p ->fail = NULL;
        return p;
    }
    /* 插入模式串，构建字典树*/
    void insertPatten()
    {
        TrieNode *p;
        p = root;
        int index = 0;
        while(patten[index] != '\0')
        {
            int lowercase = patten[index] -'a';
            if(p->son[lowercase] == NULL)
            {
                p ->son[lowercase] = createNode();
            }
            p = p->son[lowercase];
            index ++;
        }
        p ->num++;///单词末尾字符的num赋值为1，表示以它为结尾的字符串的单词数为1
    }
    /* 构建AC自动机，计算fail指针*/
    void build_AC_automaton()
    {
        TrieNode *p;
        p = root;
        queue<TrieNode*>qu;
        qu.push(p);
        while(!qu.empty())
        {
            p = qu.front();
            qu.pop();
            for(int i = 0; i < allson; i++)///将队首的儿子节点都遍历完，然后再进行下一个节点的遍历
            {
                if(p ->son[i] != NULL)///儿子节点存在
                {
                    if(p == root)///根节点下的儿子的fail指针都指向root
                        p ->son[i]->fail = root;
                    else///其他的儿子的fail指针就是找父亲的fail指针下有没有跟儿子相同的字符
                    {
                        TrieNode *node = p->fail;
                        while(node != NULL)
                        {
                            if(node ->son[i] != NULL)///有的话，就指向父亲的fail指针下的儿子节点
                            {
                                p->son[i]->fail = node->son[i];
                                break;
                            }
                            node = node->fail;
                        }
                        if(node == NULL)///没有的话就指向root
                            p->son[i]->fail = root;
                    }
                    qu.push(p->son[i]);
                }
            }
        }
    }
    /*根据文本串遍历AC自动机，查找出现多少个单词*/
    void find_in_AC_automaton()
    {
        TrieNode *p;
        p = root;
        int index = 0;
        while(text[index] != '\0')
        {
            int lowercase = text[index] - 'a';
            while(p ->son[lowercase] == NULL && p != root)
                p = p ->fail;///失配之后，转到fail指针的地方再尝试进行匹配
            p = p->son[lowercase];
            if(p == NULL) p = root;
            TrieNode *temp = p;
            while(temp != NULL && temp ->num != 0)///匹配成功时还需看看fail指针处是否也含有一个单词
            {
                ans += temp->num;
                temp ->num = 0;
                temp = temp->fail;
            }
            index++;
        }
    }
    /*链表用完都需要释放内存*/
    void freeNode(TrieNode *node)
    {
        if(node != NULL)
        {
            for(int i = 0; i < allson; i++)
                freeNode(node ->son[i]);
        }
        free(node);
    }
    int main()
    {
        int t,n;
        scanf("%d",&t);
        while(t--)
        {
            scanf("%d",&n);
            root = createNode();
            for(int i = 0; i < n; i++)
            {
                scanf("%s",patten);
                insertPatten();
            }
            scanf("%s",text);
            build_AC_automaton();
            ans = 0;
            find_in_AC_automaton();
            printf("%d\n",ans);
            freeNode(root);
        }
    }

[Link 1]: http://acm.hdu.edu.cn/showproblem.php?pid=2222