luogu3769 【模板】AC自动机（加强版）

题目大意：有N个由小写字母组成的模式串以及一个文本串T。每个模式串可能会在文本串中出现多次。你需要找出哪些模式串在文本串T中出现的次数最多。

对每个模式串建立一个Trie树。定义一个节点的Fail指针如下：如果节点x表示模式串a中字符a[i]，x->Fail表示模式串b中字符b[j]，则b[0,j]该前缀能在a[0,i]中找到与其相等的后缀。匹配时，沿trie树去匹配原串。如果trie树中当前节点cur->Next[i]==NULL，则说明当前所选择的匹配模式串不合适，由于前缀后缀的相等关系，令cur=cur->Fail转移到另一个模式串的前缀的最后一个字符表示的节点继续匹配。当前模式串的一个字符如果匹配成功，还要遍历一下cur的Fail，因为cur->Fail节点所表示的前缀可能便是整个字符串，这时便要将那些节点Sum++。

构造Fail指针方法：已知cur->Fail，设置cur->Next[i]->Fail。BFS遍历cur->Fail，如果Fail节点的Next[i]不为空，则将cur->Next[i]->Fail设为它，否则继续遍历cur->Fail->Fail，表示前缀后缀长度减小后能否匹配着。再不行就匹配到树根。

#include <cstdio>

#include <cstring>

#include <cassert>

#include <algorithm>

#include <cmath>

#include <queue>

using namespace std;

#define Ord(c) c-'a'

const int MAX_NODE = 5e5 + , MAX_SLEN = 1e6 + , MAX_CHAR = , MAX_P = , MAX_PLEN = ;

struct AC

{

    char S[MAX_SLEN], P[MAX_P][MAX_PLEN];

    int _pCnt;

    struct Node

    {

        int Sum;

        int Cnt;

        Node *Next[MAX_CHAR], *Fail;

        Node():Sum(),Cnt(){}

    }_nodes[MAX_NODE];

    Node *Root, *Tail[MAX_P];

    int _vCount;

    void Init(int pCnt)

    {

        Root = _nodes;

        memset(_nodes, , sizeof(_nodes));

        _pCnt = pCnt;

        _vCount = ;

    }

    Node *NewNode()

    {

        return _nodes + _vCount++;

    }

    Node* BuildTrie(char *s)

    {

        int len = strlen(s);

        Node *cur = Root;

        for (int p = ; p < len; p++)

        {

            if (cur->Next[Ord(s[p])])

                cur = cur->Next[Ord(s[p])];

            else

                cur = cur->Next[Ord(s[p])] = NewNode();

        }

        cur->Sum++;

        return cur;

    }

    void SetFail()

    {

        queue<Node*> q;

        q.push(Root);

        while (!q.empty())

        {

            Node *cur = q.front();

            q.pop();

            for (int i = ; i < MAX_CHAR; i++)

            {

                if (cur->Next[i])

                {

                    Node *temp = cur->Fail;

                    while (temp)

                    {

                        if (temp->Next[i])

                        {

                            cur->Next[i]->Fail = temp->Next[i];

                            break;

                        }

                        temp = temp->Fail;

                    }

                    if (!temp)

                        cur->Next[i]->Fail = Root;

                    q.push(cur->Next[i]);

                }

            }

        }

    }

    void Find()

    {

        int len = strlen(S);

        Node *cur = Root;

        for (int p = ; p < len; p++)

        {

            while (cur != Root && !cur->Next[Ord(S[p])])

                cur = cur->Fail;

            if (!(cur = cur->Next[Ord(S[p])]))

                cur = Root;

            for (Node *temp = cur; temp != Root; temp = temp->Fail)

                if (temp->Sum)

                    temp->Cnt++;

        }

    }

    void Proceed()

    {

        for (int i = ; i < _pCnt; i++)

            Tail[i] = BuildTrie(P[i]);

        SetFail();

        Find();

    }

}g;

int main()

{

#ifdef _DEBUG

    freopen("c:\\noi\\source\\input.txt", "r", stdin);

#endif

    int pCnt;

    while (scanf("%d", &pCnt) && pCnt)

    {

        g.Init(pCnt);

        for (int i = ; i < pCnt; i++)

            scanf("%s", g.P[i]);

        scanf("%s", g.S);

        g.Proceed();

        int ans = ;

        for (int i = ; i < pCnt; i++)

            ans = max(ans, g.Tail[i]->Cnt);

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

        for (int i = ; i < pCnt; i++)

            if (g.Tail[i]->Cnt == ans)

                printf("%s\n", g.P[i]);

    }

    return ;

}

巴特西

luogu3769 【模板】AC自动机（加强版）

最新文章

热门文章