题解 P3796 【【模板】AC自动机（加强版）】

· · 题解

开头小广告：自己做的一个模板库OwO

在这里HACK几乎所有的题解（因为好像没发现有对的？

4
AB
BC
CD
ABCD
ABCD
0

答案应该是

1
AB
BC
CD
ABCD

而其他同学都只输出了个别答案？？

例如

1
AB
ABCD

或

1
AB
BC
CD

会出现上面的情况，只是因为没有判断串包含的关系或者是直接退回重新匹配了

嗷？什么意思？？

举例：

  • 当匹配完串AB时：
  • 如果写的自动机不退回到B并且重新匹配（从trie树的树根开始），而是继续匹配，那么会忽略掉BC,CD两个答案，所以最终只会输出AB和ABCD这两个答案
  • 如果写的自动机退回到B重新匹配（从trie树的树根开始），那么AB,BC,CD都会匹配到，但是因为退回的关系，ABCD并没有被匹配到，这和上面的问题貌似有点矛盾了。

    上面的问题只是我自己遇到的，可能还会有其他情况，但是鉴于大多数题解并没有输出正确答案，这里给出一个我自己的解决方法：

  • 其实罪魁祸首只是退回重新匹配的时候，没有匹配到最后重新匹配了，就像匹配AB时不继续往下匹配ABCD，而是跳回根匹配B。很显然我们只要让自动机匹配到最深节点，再往回跳就对了。
  • 有的自动机直接把最深的节点下没有的节点指向了最深节点的fail
  • 可能这行代码长这样：trie[x][i] = trie[fail[x]][i];
  • 这就是我们的判断依据了，如果下一个匹配字符是跳到fail的下面的话，说明下面已经没有节点，只是我们优化连了节点而已，这个时候就可以退回trie的根重新匹配了

  • 即当trie[x][c[i+1] - 'a'] == trie[fail[x]][c[i+1] - 'a']时

    注：c[i+1]是下一个匹配字符

最后，可能这个不是唯一解决的办法，或者说会有更好AC自动机写法可以避免这个问题。这篇题解的来源是我自己打模拟赛写的自动机跑不过像这样的例子，而我自己在luogu上打的模板却AC了，于是把题解都跑了一下发现都不太正确，在此纠正一下（也有可能是自己太傻XD）

CODE

有些地方有小注释

#include <iostream>
#include <queue>
#include <vector>
#include <cstdio>
#include <cstring>
using namespace std;

const int MAXN = 1e6 + 5, MAXA = 26;
const int MAXP = 155, MAXLEN = 75;

int n;

queue<int> Q;

struct Automaton
{
    char p[MAXP][MAXLEN];

    int trie[MAXN][MAXA], fail[MAXN];
    int num[MAXN], nxt[MAXN], tot;

    signed id[MAXN][1], tail[MAXN];

    bool tag[MAXN];

    const int root = 0;

    inline void Memset(void)
    {
        memset(trie, 0, sizeof trie);
        memset(fail, 0, sizeof fail);
        memset(num, 0, sizeof num);
        memset(tag, 0, sizeof tag);
        memset(tail, 0, sizeof tail);

        return;
    }

    inline void Insert(int rak)
    {
        char *c = p[rak];
        int x = root, len = strlen(c);

        for (int i = 0; i < len; i++)
        {
            if (!trie[x][c[i] - 'a'])
                trie[x][c[i] - 'a'] = ++tot;
            x = trie[x][c[i] - 'a'];
        }
        tag[x] = true, nxt[x] = len - 1, id[x][++tail[x]] = rak;//nxt是长度-1，也是匹配到这个位置应该退回多少个字符

        return;
    }

    inline void MakeFail(void)
    {
        for (int i = 0; i < MAXA; i++)
            if (trie[root][i])
                Q.push(trie[root][i]);

        while (!Q.empty())
        {
            int x = Q.front();
            Q.pop();

            for (int i = 0; i < MAXA; i++)
            {
                if (trie[x][i])
                {
                    fail[trie[x][i]] = trie[fail[x]][i];//这里是上面讲的优化
                    Q.push(trie[x][i]);
                }
                else
                    trie[x][i] = trie[fail[x]][i];//可以依据这个判断后面是否还有节点，解决本题解讨论的问题
            }
        }

        return;
    }

    inline void Compare(char *c)
    {
        int ans = 0, x = root;

        for (int i = 0, len = strlen(c); i < len; i++)
        {
            x = trie[x][c[i] - 'a'];

            if (tag[x])
            {
                for (int j = 1; j <= tail[x]; j++)
                    ans = max(ans, ++num[id[x][j]]);

                if (trie[x][c[i+1] - 'a'] == trie[fail[x]][c[i+1] - 'a'])//题解的核心！
                    i -= nxt[x], x = root;
            }
        }

        printf("%d\n", ans);
        for (int i = 1; i <= n; i++)
            if (num[i] == ans)
                printf("%s\n", p[i]);
    }

} AC;

char s[MAXN];

signed main(void)
{
    scanf("%d", &n);
    while (n)
    {
        AC.Memset();

        for (int i = 1; i <= n; i++)
            scanf("%s", AC.p[i]), AC.Insert(i);
        AC.MakeFail();

        scanf("%s", s);
        AC.Compare(s);

        scanf("%d", &n);
    }

    return 0;
}