首页 > 其他分享 >AC自动机详解，原理、优化分析，代码实现

AC自动机详解，原理、优化分析，代码实现

时间：2024-09-22 20:54:50浏览次数：3  
标签：std AC cur int tr son 详解 fail 自动机

零、前言

对于模式串匹配问题，在很多基础的数据结构课程中都有涉及到，如 KMP 算法，BM算法，Trie。

但是给定文本串，我们有多个模式串要去查询。难道要多次调用KMP / BM，或者在Trie上多次查询吗？

Aho 和 Corasick 基于 Trie，对 KMP 进行了推广，使得 Trie 可以在一个文本串中识别一个关键字集合中的任何关键字。

这就是本博客的主题——AC自动机。

一、AC 自动机

1.1 概述

AC 自动机是 以 Trie 的结构为基础，结合 KMP 的思想 建立的自动机，用于解决多模式匹配等任务。

AC 自动机本质上是 Trie 上的自动机。

关于KMP：[KMP算法详解 c++]_kmpc+±CSDN博客

关于Trie：[Trie树/字典树的原理及实现C/C++]_trie字典树原理-CSDN博客

1.2 基本原理

建立 AC 自动机 一般分为两步：

  1. 用 所有的模式串 构建一个 Trie
  2. 为 Trie 上的所有结点构建 失配指针(fail)

1.3 Trie 构建

按照 普通 Trie 插入模式串的方式将 模式串集合中的串依次插入到Trie中

我们在Trie 上匹配模式串的过程，实质上就是在自动机上进行状态转换的过程。

因此，我们可以把Trie 的每个节点看作一个状态，每个状态事实上都对应了某个模式串的前缀。

所以下文有时会称Trie 上的节点为 前缀、状态，这里约定下。

1.4 失配指针

AC 自动机利用一个 fail 指针来辅助多模式串的匹配。

fail 指针：节点（状态） u 的 fail 指针 指向另一个 节点 v，v 是 u 的最长后缀

换句话说，v 所代表的前缀 是 u所代表的前缀的最长后缀

fail vs KMP的next

  1. 共同点：两者都是在失配时用于跳转的指针

  2. 不同点：next 指针 求的是最长公共前后缀，fail 指针则指向的是 所有模式串前缀中 和当前前缀 公共后缀最长的那个

    KMP 只对一个模式串做匹配，而AC自动机要对多个模式串做匹配。因而fail 指针可能指向的是另一个模式串，二者前缀不同。

简而言之：AC 自动机的失配指针指向当前状态的最长后缀状态。

下面先解释如何构建fail指针，再解释为何能够通过fail指针来实现多模式串匹配。

1.5 fail 指针的构建

fail 指针的构建其实就是利用 bfs 自顶向下递推的过程，从而避免了后效性。

为了方便描述，先给出节点定义：

struct AhoCorasick {
    static constexpr int ALPHABET = 26;
    static constexpr char base = 'a';
    struct Node {
        int len;    // 当前前缀长度
        int fail;   // 失配指针
        int cnt;    // 此状态结尾单词数目
        std::array<int, ALPHABET> son;  // 儿子节点
        Node(): len(0), fail(0), cnt(0), son{} {}
    };

    std::vector<Node> tr;	// 节点池
};

构建流程：

  • 队列 q 保存 bfs 过程中的节点
  • 节点 u 从队头出队，此时 u 以及 u 以上的节点的fail 都已经构建完毕
  • 遍历 u 的 儿子节点 son[i]
  • 如果 son[i] 为空，那么 son[i] 指向 fail 的 son[i]
  • 如果 son[i] 存在，那么 son[i] 的 fail 指向 u 的 fail 的 son[i]，并将 son[i] 入队
  • 队空，算法结束

由于自顶向下构建，保证了每一个节点出队时，它前面的节点都已构建完毕，保证了对子节点 fail指针构建的正确性。

事实上这是对于暴力构建fail指针的递推优化。

代码如下：

void build_fail() {
    std::queue<int> q;
    q.push(1);

    while (q.size()) {
        int u = q.front();
        q.pop();

        for (int i = 0; i < ALPHABET; ++ i) {
            if (!tr[u].son[i])
                tr[u].son[i] = tr[tr[u].fail].son[i];
            else {
                tr[tr[u].son[i]].fail = tr[tr[u].fail].son[i];
                q.push(tr[u].son[i]);
            }
        }
    }
}

放个图可以手玩一下。

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

1.6 多模式串匹配

先给出多模式串匹配的代码：

/*
	文本串: s
	模式串构建的 AC 自动机: ac
*/
int cur = 1; // 根结点编号为1
int res = 0;
for (char ch : s) {
    cur = ac.son(cur, ch - 'a');	// 往下跳一步
    // 开始跳fail，遍历所有后缀
    for (int newcur = cur; newcur && ac.cnt(newcur) >= 0; newcur = ac.fail(newcur)) {
        res += ac.cnt(newcur), ac.cnt(newcur) = -1;
    }
}
  • 默认从根节点开始匹配s
  • 当前节点号为cur
  • 遍历到字符ch
  • cur = son[ch]
    • son[ch] 要么是成功匹配节点，要么是 构建fail 时 指向的最长后缀的 son[ch]
  • 然后从 cur 开始跳fail，将所有后缀节点都跑一遍，记录匹配

事实上，大部分 编译原理 课程中都会介绍最长匹配原则，保证了我们的匹配不漏，这点可以自行了解。

1.7 后缀链接优化

尝试自己模拟下这组样例：

target 为文本串，words 为 模式串集合

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

发现复杂度会爆炸的

巧妙的是，KMP算法中也对nxt 数组进行了优化，我们这里也是利用类似思想来进行优化。

这里引入后缀链接(link)：

后缀链接（suffix link），用来快速跳到一定是某个 模式串 的最后一个字母的节点（等于 root 则表示没有）

这样一来节点定义如下：

struct Node {
    std::vector<int> id;
    int len;
    int fail;
    int last;
    std::array<int, ALPHABET> son;
    Node() : last(0), id{}, len(0), fail(0), son{} {}
};

构建过程：

last 是和 fail 在一起构建的：

根节点的 last 默认指向 根节点

  • 继承前面bfs 构建fail 的逻辑
  • u出队，此时u 以及前面的 fail 和 last 都已经构建完毕
  • 遍历 u 的 儿子节点 son[i]
  • 如果 son[i] 为空，那么 son[i] 指向 fail 的 son[i]
  • 如果 son[i] 存在，那么 son[i] 的 fail 指向 u 的 fail 的 son[i]
    • 如果 son[i].fail 是单词结尾，那么 son[i].last = son[i].fail，否则指向 son[i].fail.last
    • 将 son[i] 入队
  • 队空，算法结束

代码如下：

void build() {
    std::queue<int> q;
    q.push(1);
    while (q.size()) {
        int u = q.front();
        q.pop();

        for (int i = 0; i < ALPHABET; ++ i) {
            if (!tr[u].son[i]) {
                tr[u].son[i] = tr[tr[u].fail].son[i];
                continue;
            }
            tr[tr[u].son[i]].fail = tr[tr[u].fail].son[i];
            tr[tr[u].son[i]].last = tr[tr[tr[u].son[i]].fail].cnt ? 
                tr[tr[u].son[i]].fail : tr[tr[tr[u].son[i]].fail].last;
            q.push(tr[u].son[i]);
        }
    }
}

1.8 拓扑优化

见OJ练习2.3

1.9 dfs 优化

见OJ练习2.3

二、OJ 练习

2.1 P3808 AC 自动机（简单版I）

原题链接

P3808 AC 自动机（简单版） - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

思路分析

如果暴力跳 fail 或者 last 都会TLE，我们对于走过的点打个标记，即 cnt = -1

AC代码

#include <bits/stdc++.h>
// #include <ranges>

using u32 = unsigned;
using i64 = long long;
using u64 = unsigned long long;

constexpr int P = 1E9 + 7;;
constexpr int inf32 = 1E9 + 7;
constexpr i64 inf64 = 1E18 + 7;

struct AhoCorasick {
    static constexpr int ALPHABET = 26;
    static constexpr char base = 'a';
    struct Node {
        int len;    // 当前前缀长度
        int fail;   // 失配指针
        int cnt;    // 此状态结尾单词数目
        int last;   // 后缀链接
        std::array<int, ALPHABET> son;  // 儿子节点
        Node(): last{0}, len(0), fail(0), cnt(0), son{} {}
    };

    std::vector<Node> tr;

    AhoCorasick() {
        init();
    }

    void init() {
        tr.assign(2, Node());
        tr[0].son.fill(1);
        tr[0].len = -1;
        tr[0].last = 1;
    }

    int newNode() {
        tr.emplace_back();
        return (int)tr.size() - 1;
    }

    int add(const std::string &s) {
        int cur = 1;
        for (char ch : s) {
            int x = ch - base;
            if (!tr[cur].son[x]) {
                tr[cur].son[x] = newNode();
                tr[tr[cur].son[x]].len = tr[cur].len + 1;
            }
            cur = tr[cur].son[x];
        }
        ++ tr[cur].cnt;
        return cur;
    }

    void work() {
        std::queue<int> q;
        q.push(1);

        while (q.size()) {
            int u = q.front();
            q.pop();

            for (int i = 0; i < ALPHABET; ++ i) {
                if (!tr[u].son[i]) {
                    tr[u].son[i] = tr[tr[u].fail].son[i];
                    continue;
                }
                tr[tr[u].son[i]].fail = tr[tr[u].fail].son[i];
                tr[tr[u].son[i]].last = tr[tr[tr[u].son[i]].fail].cnt > 0 ? tr[tr[u].son[i]].fail : tr[tr[tr[u].son[i]].fail].last;
                q.push(tr[u].son[i]);
            }
        }
    }

    int son(int cur, int x) const{
        return tr[cur].son[x];
    }

    int fail(int cur) const{
        return tr[cur].fail;
    }

    int len(int cur) const{
        return tr[cur].len;
    }

    int size() const{
        return tr.size();
    }

    int last(int cur) const {
        return tr[cur].last;
    }

    int& cnt(int cur) {
        return tr[cur].cnt;
    }
};


void solve() {
    int n;
    std::cin >> n;

    AhoCorasick ac;
    for (int i = 0; i < n; ++ i) {
        std::string s;
        std::cin >> s;
        ac.add(s);
    }

    ac.work();

    std::string t;
    std::cin >> t;

    int res = 0;
    for (int i = 0, cur = 1; i < t.size(); ++ i) {
        cur = ac.son(cur, t[i] - 'a');
        for (int ncur = cur; ncur && ac.cnt(ncur) >= 0; ncur = ac.last(ncur)) {
            res += ac.cnt(ncur);
            ac.cnt(ncur) = -1;
        }
    }

    std::cout << res << '\n';
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int t = 1;
    // std::cin >> t;
    
    while (t--) {
        solve();
    }
    
    return 0;
}

2.2 P3796 AC 自动机（简单版 II）

原题链接

P3796 AC 自动机（简单版 II） - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

思路分析

也是板题，额外存个id就行

AC代码

#include <bits/stdc++.h>
// #include <ranges>

using u32 = unsigned;
using i64 = long long;
using u64 = unsigned long long;

constexpr int P = 1E9 + 7;;
constexpr int inf32 = 1E9 + 7;
constexpr i64 inf64 = 1E18 + 7;

struct AhoCorasick{
    static constexpr int ALPHABET = 26;
    static constexpr char base = 'a';

    struct Node{
        int len;
        int cnt;
        int fail;
        int last;
        int id;
        std::array<int, ALPHABET> son;
        Node(): len{0}, cnt{0}, fail{0}, last{0}, id{-1}, son{} {}
    };

    std::vector<Node> tr;

    AhoCorasick() {
        init();
    }

    void init() {
        tr.assign(2, Node());
        tr[0].son.fill(1);
        tr[0].len = -1;
        tr[0].last = 1;
    }

    int newNode() {
        tr.emplace_back();
        return (int)tr.size() - 1;
    }

    int add(const std::string &s, int id) {
        int cur = 1;
        for (char ch : s) {
            int x = ch - base;
            if (!tr[cur].son[x]) {
                tr[cur].son[x] = newNode();
                tr[tr[cur].son[x]].len = tr[cur].len + 1;
            }
            cur = tr[cur].son[x];
        }
        ++ tr[cur].cnt;
        tr[cur].id = id;
        return cur;
    }

    void work() {
        std::queue<int> q;
        q.push(1);

        while (q.size()) {
            int u = q.front();
            q.pop();
            for (int i = 0; i < ALPHABET; ++ i) {
                if (!tr[u].son[i]) {
                    tr[u].son[i] = tr[tr[u].fail].son[i];
                    continue;
                }
                tr[tr[u].son[i]].fail = tr[tr[u].fail].son[i];
                tr[tr[u].son[i]].last = tr[tr[tr[u].son[i]].fail].cnt > 0 ? tr[tr[u].son[i]].fail : tr[tr[tr[u].son[i]].fail].last;
                q.push(tr[u].son[i]);
            }
        }
    }

    int cnt(int cur) const{
        return tr[cur].cnt;
    }

    int len(int cur) const{
        return tr[cur].len;
    }

    int fail(int cur) const{
        return tr[cur].fail;
    }

    int son(int cur, int x) const{
        return tr[cur].son[x];
    }

    int last(int cur) const{
        return tr[cur].last;
    }

    int id(int cur) const{
        return tr[cur].id;
    }
};

void solve() {
    int n;
    while (std::cin >> n, n)  {
        AhoCorasick ac;
        std::vector<std::string> words(n);
        for (int i = 0; i < n; ++ i) {
            std::cin >> words[i];
            ac.add(words[i], i);
        }

        ac.work();

        std::string t;
        std::cin >> t;

        std::vector<int> cnt(n);
        int cur = 1;
        for (char ch : t) {
            int x = ch - 'a';
            cur = ac.son(cur, x);
            for (int newcur = cur; newcur > 1; newcur = ac.last(newcur))
                if (~ac.id(newcur))
                    ++ cnt[ac.id(newcur)];
        }

        int ma = *std::max_element(cnt.begin(), cnt.end());

        std::cout << ma << '\n';
        for (int i = 0; i < n; ++ i)
            if (cnt[i] == ma)
                std::cout << words[i] << '\n';
    }
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int t = 1;
    // std::cin >> t;
    
    while (t--) {
        solve();
    }
    
    return 0;
}

2.3 P5357 【模板】AC 自动机（拓扑&dfs优化）

原题链接

P5357 【模板】AC 自动机 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

思路分析

用后缀链接优化可以跑到84分，我们这个时候有两个选择：

  • 拓扑优化
  • dfs 优化

二者其实思想相同，只不过一个实现方式是bfs拓扑排序，一个是dfs（类似树形dp）

我们看这个样例图：

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

如果我们把fail 边抽离出来会得到什么？

一棵树

因为一个节点只有一条fail边

那么我们按照fail边建树，有两种方式，一个是不改变原图的fail方向，一个是翻转原图fail方向

两种方式分别对应了拓扑和dfs的做法

那么我们在文本串上匹配，每匹配一个字符，自动机都会跳转到一个状态，我们将该状态贡献+1

那么每个模式串都对应着AC自动机上的一个状态节点

每个模式串在文本串中出现次数 就是 从该状态节点，沿着fail边反方向所能到达节点的贡献和

因而我们可以：

  • 不改变fail边方向建树，进行拓扑排序，在拓扑排序的时候将贡献往后累加
  • 改变fail边方向建树，进行dfs，树形dp计数

AC代码

拓扑优化：

#include <bits/stdc++.h>
// #include <ranges>

using u32 = unsigned;
using i64 = long long;
using u64 = unsigned long long;

constexpr int P = 1E9 + 7;;
constexpr int inf32 = 1E9 + 7;
constexpr i64 inf64 = 1E18 + 7;

struct AhoCorasick{
    static constexpr int ALPHABET = 26;
    static constexpr char base = 'a';

    struct Node{
        int len;
        int cnt;
        int fail;
        int last;
        int in;
        std::array<int, ALPHABET> son;
        Node(): len{0}, cnt{0}, fail{0}, last{0}, in{0}, son{} {}
    };

    std::vector<Node> tr;

    AhoCorasick() {
        init();
    }

    void init() {
        tr.assign(2, Node());
        tr[0].son.fill(1);
        tr[0].len = -1;
        tr[0].last = 1;
    }

    int newNode() {
        tr.emplace_back();
        return (int)tr.size() - 1;
    }

    int add(const std::string &s) {
        int cur = 1;
        for (char ch : s) {
            int x = ch - base;
            if (!tr[cur].son[x]) {
                tr[cur].son[x] = newNode();
                tr[tr[cur].son[x]].len = tr[cur].len + 1;
            }
            cur = tr[cur].son[x];
        }
        ++ tr[cur].cnt;
        return cur;
    }

    void work() {
        std::queue<int> q;
        q.push(1);

        while (q.size()) {
            int u = q.front();
            q.pop();
            for (int i = 0; i < ALPHABET; ++ i) {
                if (!tr[u].son[i]) {
                    tr[u].son[i] = tr[tr[u].fail].son[i];
                    continue;
                }
                tr[tr[u].son[i]].fail = tr[tr[u].fail].son[i];
                ++ tr[tr[tr[u].son[i]].fail].in;
                tr[tr[u].son[i]].last = tr[tr[tr[u].son[i]].fail].cnt > 0 ? tr[tr[u].son[i]].fail : tr[tr[tr[u].son[i]].fail].last;
                q.push(tr[u].son[i]);
            }
        }
    }

    int cnt(int cur) const{
        return tr[cur].cnt;
    }

    int len(int cur) const{
        return tr[cur].len;
    }

    int fail(int cur) const{
        return tr[cur].fail;
    }

    int son(int cur, int x) const{
        return tr[cur].son[x];
    }

    int last(int cur) const{
        return tr[cur].last;
    }

    int &in(int cur) {
        return tr[cur].in;
    }

    int size() const{
        return tr.size();
    }
};

void solve() {
    int n;
    std::cin >> n;
    AhoCorasick ac;
    std::vector<int> end(n);
    for (int i = 0; i < n; ++ i) {
        std::string s;
        std::cin >> s;
        end[i] = ac.add(s);
    }
    ac.work();

    std::string t;
    std::cin >> t;

    std::vector<int> f(ac.size());
    int cur = 1;
    for (char ch : t) {
        cur = ac.son(cur, ch - 'a');
        ++ f[cur];
    }

    std::queue<int> q;
    for (int i = 2; i < ac.size(); ++ i)
        if (!ac.in(i))
            q.push(i);

    while (q.size()) {
        int u = q.front();
        q.pop();

        f[ac.fail(u)] += f[u];
        if (! -- ac.in(ac.fail(u)))
            q.push(ac.fail(u));
    }

    for (int i = 0; i < n; ++ i)
        std::cout << f[end[i]] << '\n';
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int t = 1;
    // std::cin >> t;
    
    while (t--) {
        solve();
    }
    
    return 0;
}

dfs优化：

#include <bits/stdc++.h>
// #include <ranges>

using u32 = unsigned;
using i64 = long long;
using u64 = unsigned long long;

constexpr int P = 1E9 + 7;;
constexpr int inf32 = 1E9 + 7;
constexpr i64 inf64 = 1E18 + 7;

struct AhoCorasick{
    static constexpr int ALPHABET = 26;
    static constexpr char base = 'a';

    struct Node{
        int len;
        int cnt;
        int fail;
        int last;
        std::array<int, ALPHABET> son;
        Node(): len{0}, cnt{0}, fail{0}, last{0}, son{} {}
    };

    std::vector<Node> tr;

    AhoCorasick() {
        init();
    }

    void init() {
        tr.assign(2, Node());
        tr[0].son.fill(1);
        tr[0].len = -1;
        tr[0].last = 1;
    }

    int newNode() {
        tr.emplace_back();
        return (int)tr.size() - 1;
    }

    int add(const std::string &s) {
        int cur = 1;
        for (char ch : s) {
            int x = ch - base;
            if (!tr[cur].son[x]) {
                tr[cur].son[x] = newNode();
                tr[tr[cur].son[x]].len = tr[cur].len + 1;
            }
            cur = tr[cur].son[x];
        }
        ++ tr[cur].cnt;
        return cur;
    }

    void work() {
        std::queue<int> q;
        q.push(1);

        while (q.size()) {
            int u = q.front();
            q.pop();
            for (int i = 0; i < ALPHABET; ++ i) {
                if (!tr[u].son[i]) {
                    tr[u].son[i] = tr[tr[u].fail].son[i];
                    continue;
                }
                tr[tr[u].son[i]].fail = tr[tr[u].fail].son[i];
                tr[tr[u].son[i]].last = tr[tr[tr[u].son[i]].fail].cnt > 0 ? tr[tr[u].son[i]].fail : tr[tr[tr[u].son[i]].fail].last;
                q.push(tr[u].son[i]);
            }
        }
    }

    int cnt(int cur) const{
        return tr[cur].cnt;
    }

    int len(int cur) const{
        return tr[cur].len;
    }

    int fail(int cur) const{
        return tr[cur].fail;
    }

    int son(int cur, int x) const{
        return tr[cur].son[x];
    }

    int last(int cur) const{
        return tr[cur].last;
    }

    int size() const{
        return tr.size();
    }
};

void solve() {
    int n;
    std::cin >> n;
    AhoCorasick ac;
    std::vector<int> end(n);
    for (int i = 0; i < n; ++ i) {
        std::string s;
        std::cin >> s;
        end[i] = ac.add(s);
    }
    ac.work();

    std::string t;
    std::cin >> t;

    std::vector<int> f(ac.size());
    int cur = 1;
    for (char ch : t) {
        cur = ac.son(cur, ch - 'a');
        ++ f[cur];
    }

    std::vector<std::vector<int>> adj(ac.size());

    for (int i = 2; i < ac.size(); ++ i)
        adj[ac.fail(i)].push_back(i);

    auto dfs = [&](auto &&self, int x) -> void {
        for (int y : adj[x]) {
            self(self, y);
            f[x] += f[y];
        }
    };

    dfs(dfs, 1);

    for (int i = 0; i < n; ++ i)
        std::cout << f[end[i]] << '\n';
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int t = 1;
    // std::cin >> t;
    
    while (t--) {
        solve();
    }
    
    return 0;
}

2.4 L语言

原题链接

https://www.luogu.com.cn/problem/P2292

思路分析

对于每个 字符串t，我们要判断其是否可以由给定的字符串集合构造出来

那么考虑dp

定义 f(i) 为 t 的前 i 个字符是否可以被构造

那么 f(i) = f(i - len(s1)) || f(i - len(s2))…

其中 si 为 t[1, i] 的 后缀，且 si 在字符串集合中

对于 si 的获取我们可以跳 last 来快速获取

这个题比较 sb 的是洛谷加数据了，题解很多用的状态压缩，实际上不用

我们加两个剪枝：

记 ma 为最长匹配前缀长度

  • 如果 i - ma > 20，我们就break（因为 s 最长也就20）
  • 如果 f[i] 已经为 true，我们就不跳last

AC代码

#include <bits/stdc++.h>
// #include <ranges>

using u32 = unsigned;
using i64 = long long;
using u64 = unsigned long long;

constexpr int P = 1E9 + 7;;
constexpr int inf32 = 1E9 + 7;
constexpr i64 inf64 = 1E18 + 7;

struct AhoCorasick{
    static constexpr int ALPHABET = 26;
    static constexpr char base = 'a';

    struct Node{
        int len;
        int cnt;
        int fail;
        int last;
        std::array<int, ALPHABET> son;
        Node(): len{0}, cnt{0}, fail{0}, last{0}, son{} {}
    };

    std::vector<Node> tr;

    AhoCorasick() {
        tr.reserve(10000);
        init();
    }

    void init() {
        tr.assign(2, Node());
        tr[0].son.fill(1);
        tr[0].len = -1;
        tr[0].last = 1;
    }

    int newNode() {
        tr.emplace_back();
        return (int)tr.size() - 1;
    }

    int add(const std::string &s) {
        int cur = 1;
        for (char ch : s) {
            int x = ch - base;
            if (!tr[cur].son[x]) {
                tr[cur].son[x] = newNode();
                tr[tr[cur].son[x]].len = tr[cur].len + 1;
            }
            cur = tr[cur].son[x];
        }
        ++ tr[cur].cnt;
        return cur;
    }

    void work() {
        std::queue<int> q;
        q.push(1);

        while (q.size()) {
            int u = q.front();
            q.pop();
            for (int i = 0; i < ALPHABET; ++ i) {
                if (!tr[u].son[i]) {
                    tr[u].son[i] = tr[tr[u].fail].son[i];
                    continue;
                }
                tr[tr[u].son[i]].fail = tr[tr[u].fail].son[i];
                tr[tr[u].son[i]].last = tr[tr[tr[u].son[i]].fail].cnt > 0 ? 
                    tr[tr[u].son[i]].fail : tr[tr[tr[u].son[i]].fail].last;
                q.push(tr[u].son[i]);
            }
        }
    }

    int cnt(int cur) const{
        return tr[cur].cnt;
    }

    int len(int cur) const{
        return tr[cur].len;
    }

    int fail(int cur) const{
        return tr[cur].fail;
    }

    int son(int cur, int x) const{
        return tr[cur].son[x];
    }

    int last(int cur) const{
        return tr[cur].last;
    }

    int size() const{
        return tr.size();
    }
};

void solve() {
    int n, m;
    std::cin >> n >> m;

    AhoCorasick ac;
    for (int i = 0; i < n; ++ i) {
        std::string s;
        std::cin >> s;
        ac.add(s);
    }

    ac.work();

    for (int i = 0; i < m; ++ i) {
        std::string t;
        std::cin >> t;
        n = t.size();
        std::vector<bool> f(n + 1);
        f[0] = true;
        int cur = 1;
        int ma = 0;
        for (int i = 1; i <= n; ++ i) {
            cur = ac.son(cur, t[i - 1] - 'a');
            for (int newcur = cur; newcur > 1; newcur = ac.last(newcur)) {
                if (f[i]) break;
                if (ac.cnt(newcur)) {
                    f[i] = f[i] || f[i - ac.len(newcur)];
                }
            }
            if (f[i]) ma = i;
            if (i - ma > 20) break;
        }
        std::cout << ma << '\n';
    }

}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int t = 1;
    // std::cin >> t;
    
    while (t--) {
        solve();
    }
    
    return 0;
}

标签：std,AC,cur,int,tr,son,详解,fail,自动机
From： https://blog.csdn.net/EQUINOX1/article/details/142420788

相关文章

  • [HKEY_LOCAL_MACHINE\SYSTEM\ControlSet001\Services\partmgr\Parameters] "SanP
    WindowsRegistryEditorVersion5.00;关闭windowstogo特性[HKEY_LOCAL_MACHINE\SYSTEM\ControlSet001\Control]"PortableOperatingSystem"=dword:00000000 [HKEY_LOCAL_MACHINE\SYSTEM\ControlSet001\Services\partmgr\Parameters]"SanPolicy"=......
  • [CVPR2024]DeiT-LT Distillation Strikes Back for Vision Transformer Training on L
    在长尾数据集上，本文引入强增强（文中也称为OOD）实现对DeiT的知识蒸馏的改进，实现尾部类分类性能的提升。动机ViT相较于CNN缺少归纳偏置，如局部性（一个像素与周围的区域关系更紧密）、平移不变性（图像的主体在图像的任意位置都应该一样重要）。因此需要大型数据集进行预训练。长尾数据学习......
  • [20240920]跟踪library cache lock library cache pin使用gdb.txt
    [20240920]跟踪librarycachelocklibrarycachepin使用gdb.txt--//前一阵子，写的使用gdb跟踪librarycachelocklibrarycachepin的脚本有一个小问题，无法获得lockaddress以及pinaddress--//地址,有一点点小缺陷，尝试修改完善看看。--//按照https://nenadnoveljic.com/blog/tr......
  • 2024睿抗机器人开发者大赛CAIP-编程技能赛-本科组（省赛） RC-u5 工作安排详解
    本文参考https://www.cnblogs.com/Kescholar/p/18306136这一题可能对高手来说就能轻而易举的看出是个01背包，但是对于我这种小白还是要经过详细的分析才可以理解。我们题目要求的是获得的最大报酬，题目的影响因素有三个：工作时长、工作截止时间、对应的报酬，那么怎么样合理的去......
  • Metric3D v2: A Versatile Monocular Geometric Foundation Model for Zero-shot Metr
    paperMetric3Dv2:AVersatileMonocularGeometricFoundationModelforZero-shotMetricDepthandSurfaceNormalEstimation作者MuHu1∗,WeiYin2∗†,ChiZhang3,ZhipengCai4,XiaoxiaoLong5‡,HaoChen6,KaixuanWang1,GangYu7,ChunhuaShen......
  • 开放食物营养库python SDK套件：openfoodfacts-python
    官网源码：GitHub-openfoodfacts/openfoodfacts-python:......
  • ConcurrentLinkedQueue详解(图文并茂)
    前言ConcurrentLinkedQueue是基于链接节点的无界线程安全队列。此队列按照FIFO（先进先出）原则对元素进行排序。队列的头部是队列中存在时间最长的元素，而队列的尾部则是最近添加的元素。新的元素总是被插入到队列的尾部，而队列的获取操作（例如poll或peek）则是从队列头部开始。与传统的L......
  • Oracle2PG sequence(序列）问题汇总
    迁移PostgreSQL的Sequence（序列）问题https://masuit.net/2042?t=0HN6FQRQT1K6P如何快速获取同步序列的SQL有些项目中数据量比较少，在迁移过程；表数据迁移过去；但是序列需要重置下；接下来讲到，引用自：https://www.cnblogs.com/lottu/p/14330474.htmlSELECTconcat('SELECTsetval(''"',......
  • ConcurrentLinkedQueue详解(图文并茂)
    前言ConcurrentLinkedQueue是基于链接节点的无界线程安全队列。此队列按照FIFO（先进先出）原则对元素进行排序。队列的头部是队列中存在时间最长的元素，而队列的尾部则是最近添加的元素。新的元素总是被插入到队列的尾部，而队列的获取操作（例如poll或peek）则是从队列头部开始。与传统的......
  • 综合靶场 DC-1 通关详解
    一、环境搭建：1、靶机描述DC-1是一个专门建立的脆弱实验室，目的是获得渗透测试领域的经验。它是为初学者设计的挑战，但它到底有多容易取决于你的技能和知识，以及你的学习能力。要成功完成这一挑战，您需要掌握Linux技能，熟悉Linux命令行，并具有基本渗透测试工具的经验，例如可以在Kali......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99