ACautomaton
|
1.3k 字
|
5 分钟

AC自动机

阅读本章之前应该具备的前置知识：KMP（其实并不是很重要但是还是要会的），trie字典树

首先对于若干的模式串我们把它插入到一个trie树中，我们考虑，对于一个非常水的模板题：

对于一个文本串，计算所有模式串在其中出现次数的总和

我们考虑把这个文本串在这个trie树上面跑一遍（像是插入一样

但是我们发现，如果说我们当前匹配的时候发现失配了，根据KMP自动机的思想来说，我们应该找尽量长的已经匹配了的长度，那么这在trie树上面就应该对应的是：已经匹配了的这个字符串的最长后缀

因为我们的trie树上每一个节点都对应着一个字符串，那么我们可以通过将一个节点指向另一个节点来代表最长后缀，这就是AC自动机的核心：fail指针

我们在求fail指针的时候，如果说这个节点要求fail指针，那么指向的节点一定是最长后缀，那么，这个节点的父亲的fail指针的这个字符节点也就是这个节点的fail指针，就是：fail[t[p][i]]=t[fail[p]][i]fail[t[p][i]]=t[fail[p]][i]

意会一下

题目：

P3808 【模板】AC 自动机（简单版）

板子题

我们在文本串进行匹配的时候看一下有多少个点在匹配的时候是一个字符串的结束节点，就说明这个字符串被匹配过了

#include <bits/stdc++.h>
using namespace std;

const int maxn = 1e6 + 10;

int fail[maxn], t[maxn][26], cnt, en[maxn];
int n;
string s;

void add(string s)
{
    int p = 0;
    for (int i = 0; i < s.size(); i++)
    {
        int ch = s[i] - 'a';
        if (!t[p][ch])
            t[p][ch] = ++cnt;
        p = t[p][ch];
    }
    en[p]++;
}

void build()
{
    queue<int> q;
    for (int i = 0; i < 26; i++)
        if (t[0][i])
            q.push(t[0][i]);
    while (!q.empty())
    {
        int p = q.front();
        q.pop();
        for (int i = 0; i <= 25; i++)
        {
            if (t[p][i])
                fail[t[p][i]] = t[fail[p]][i], q.push(t[p][i]);
            else
                t[p][i] = t[fail[p]][i];
        }
    }
}

int ask(string s)
{
    int p = 0, ans = 0, len = s.size();
    for (int i = 0; i < len; i++)
    {
        int ch = s[i] - 'a';
        p = t[p][ch];
        ans += en[p];
        en[p] = 0;
    }
    return ans;
}

signed main()
{
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif
    ios::sync_with_stdio(false);
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> s;
        add(s);
    }
    cout << cnt << endl;
    build();
    cin >> s;
    cout << ask(s) << endl;
    return 0;
}

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

每一次匹配到一个结束节点的时候，把这个结束节点对应的字符串的位置cnt加一

然后打擂台求最大，然后输出，要按顺序

P3121 [USACO15FEB]Censoring G

每一次匹配到一个结束节点就对应的删掉这个字符串

删掉字符串用什么呢？

栈！

如果说我们删掉这个字符串就是对应的把这个字符串从栈里去掉，每一个字符最多会被去掉一次所以复杂度是可以保证的

P3966 [TJOI2013]单词

我们在AC自动机上面记录一下每一个字符属于多少个字符串，这个直接fail树求子树和

求子树和的时候是可以用我们在求fail指针的时候求出来的bfs序列倒叙求子树和的

求出来子树和之后，这个单词出现了多少次不也就出来了吗

因为我们求的是出现了多少次，所以直接求出来它属于多少个字符串就可以了

P2444 [POI2000]病毒

这个题思路倒是挺清奇，不同寻常

如果说我们正难则反，先考虑把一个无限长的序列放在AC自动机上面跑一遍，那么说明，一定会出现一个循环使得AC自动机无限跑，如果不是的话，就一定会和病毒序列进行匹配

那么问题就转化成了能不能在AC自动机上面找到一个环（前提是这个AC自动机是用的trie图写法，就是把一个空结点指向fail指针的当前字符节点）

跑一遍dfs就好了

P4052 [JSOI2007]文本生成器

AC自动机上面跑dp的板子题了属于是

我们考虑一下：正难则反容斥，总方案数减去不合法

设dp函数fi,jf_{i,j}表示当前串的长度为i，AC自动机上面是在j节点的不合法方案数

我们会发现，fi+1.t[j][p]f_{i+1.t[j][p]}是可以通过fi,jf_{i,j}进行转移的，只要这个节点是合法的，合法指的是后缀不是生成的文本其中之一，就是说，他自己和fail树里的节点里面没有一个是字符串的结尾节点

然后转移到最后用26m26^m减去上面的不合法方案数就是答案

完结（暂时）

上一篇
下一篇