hdoj 2222 Keywords Search(AC自动机)

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2222

思路分析：该问题为多模式匹配问题，使用AC自动机解决；需要注意的问题是如何统计该待查询的字符串包含的关键字：

假设待查找的字符串为str[0..n]，则str[i…j]可能为某一个关键字；假设当前正在匹配字符str[k],则以str[i..k]为关键字的所有可能

可能的关键字的最后一个字符为str[k]，使用fail指针进行跳转并判断以str[k]结尾的该结点是否为关键字最后一个结点，重复进行该

操作直到回溯到根节点。

代码如下：

#include <cstdio>

#include <cstring>

#include <iostream>

using namespace std;

const int KIND = ;

const int LEN_STR =  + ;

const int MAX_N =  + ;

struct Node;

Node *q[MAX_N];

char insert_str[LEN_STR];

char str[MAX_N];

struct Node {

    Node *fail;

    Node *next[KIND];

    int count;

    Node()

    {

        fail = NULL;

        count = ;

        memset(next, NULL, sizeof(next));

    }

};

void Insert(char *str, Node *root)

{

    Node *p = root;

    int i = , index = ;

    while (str[i]) {

        index = str[i++] - 'a';

        if (p->next[index] == NULL)

            p->next[index] = new Node();

        p = p->next[index];

    }

    p->count++; // 单词的末尾会被标记为1

}

void BuildAcAutomation(Node *root)

{

    int head = , tail = ;

    root->fail = NULL;

    q[tail++] = root;

    while (head != tail) {

        Node *temp = q[head++];

        Node *p = NULL;

        for (int i = ; i < KIND; ++i) {

            if (temp->next[i]) {

                if (temp == root)

                    temp->next[i]->fail = root;

                else {

                    p = temp->fail;

                    while (p != NULL) {

                        if(p->next[i]) {

                            temp->next[i]->fail = p->next[i];

                            break;

                        }

                        p = p->fail;

                    }

                    if (p == NULL)

                        temp->next[i]->fail = root;

                }

                q[tail++] = temp->next[i];

            }

        }

    }

}

int Query(char *str, Node *root)

{

    int i = , cnt = , index = ;

    Node *p = root;

    while (str[i]) {

        index = str[i] - 'a';

        while (!p->next[index] && p != root)

            p = p->fail;

        p = p->next[index];

        p = (p == NULL) ? root : p;

        Node *temp = p;

        while (temp != root && temp->count != -) {

            cnt += temp->count;

            temp->count = -;

            temp = temp->fail;

        }

        ++i;

    }

    return cnt;

}

int main()

{

    int case_times = ;

    int ans = , n = ;

    scanf("%d", &case_times);

    while (case_times--) {

        Node *root = new Node();

        scanf("%d", &n);

        while (n--) {

            scanf("%s", insert_str);

            Insert(insert_str, root);

        }

        BuildAcAutomation(root);

        scanf("%s", &str);

        ans = Query(str, root);

        printf("%d\n", ans);

    }

    return ;

}

巴特西

hdoj 2222 Keywords Search(AC自动机)

最新文章

热门文章