AC自动机实现与应用

问题背景

我们需要处理n个字符串，每个字符串的权值初始为0。通过m次操作，操作有两种类型：

类型(1 i x)：将第i个字符串的权值设为x。

类型(2 q)：在n个字符串中找到一个最大权值的字符串q的子串，满足这个子串是q本身的子串。如果不存在这样的子串，输出-1。

解决方案

为高效处理上述操作，我们采用AC自动机（即Aho-Corasick算法）的方法。具体做法如下：

AC自动机构建：

将所有字符串预处理，构建AC自动机的各个节点。

每个节点维护一个多集合（multiset），用于存储当前节点的最大权值。

更新操作：

当执行类型(1)操作时，直接更新对应的字符串的权值，并在AC自动机中更新多集合中的值。

查询操作：

对于类型(2)操作，沿着AC自动机的跳转链，逐层查询经过的节点的多集合，取最大值即可得到结果。

详细实现

AC自动机结构

节点结构：

每个节点包含一个大小为26的字母表数组a，用于存储该节点的子节点。

每个节点还包含ed_pos，记录该节点对应的输入字符串的位置。

val用于存储该节点的当前权值。

last用于记录该节点的终结跳转节点。

ss数组用于存储各节点的多集合，用于维护最大值。

构建过程：

初始化失败函数fail，建立基本的跳转链。

使用广度优先搜索（BFS）构建完整的跳转链。

对每个节点的多集合进行初始化，确保每个节点都有一个初始值。

更新过程：

通过update函数更新节点的权值，并在多集合中进行插入和删除操作，保持多集合的正确性。

查询过程：

在ask函数中，沿着AC自动机的跳转链遍历，查询每个节点的多集合，取最大值即可得到结果。

代码实现示例

#include 
   
    using namespace std;const int maxm = 3e5 + 5;char s[maxm];struct AC {    int a[maxm][26];    int ed_pos[maxm];    int val[maxm];    int fail[maxm];    int last[maxm];    int tot;    multiset
    
      ss[maxm];    void add(char *s, int idx) {        int node = 0;        for (int i = 0; s[i]; ++i) {            int v = s[i] - 'a';            if (!a[node][v]) {                a[node][v] = ++tot;                node = a[node][v];            } else {                node = a[node][v];            }        }        ed_pos[idx] = node;        val[idx] = 0;        ss[node].insert(val[idx]);    }    void build() {        for (int i = 0; i <= tot; ++i) {            ss[i].insert(-1);        }        queue
     
       q;        for (int i = 0; i < 26; ++i) {            if (a[0][i]) {                fail[a[0][i]] = 0;                q.push(a[0][i]);            }        }        while (!q.empty()) {            int x = q.front();            q.pop();            last[x] = (ss[fail[x]].rbegin() > ss[x].rbegin()) ? fail[x] : last[fail[x]];            for (int i = 0; i < 26; ++i) {                if (a[x][i]) {                    fail[a[x][i]] = a[fail[x]][i];                    q.push(a[x][i]);                } else {                    a[x][i] = a[fail[x]][i];                }            }        }    }    void update(int idx, int x) {        int pos = ed_pos[idx];        ss[pos].erase(ss[pos].find(val[idx]));        val[idx] = x;        ss[pos].insert(val[idx]);    }    int ask(char *s) {        int ans = -1;        int node = 0;        for (int i = 0; s[i]; ++i) {            int v = s[i] - 'a';            node = a[node][v];            for (int t = node; t != last[node]; ++t) {                ans = max(ans, *ss[t].rbegin());            }        }        return ans;    }};int main() {    scanf("%d%d", &n, &m);    for (int i = 1; i <= n; ++i) {        scanf("%s", s);    }    AC ac;    ac.add(s, 1);    ac.build();    while (m--) {        int op;        scanf("%d", &op);        if (op == 1) {            int i, x;            scanf("%d%d", &i, &x);            ac.update(i, x);        } else {            scanf("%s", s);            int ans = ac.ask(s);            printf("%d\n", ans);        }    }    return 0;}

代码解释

AC结构：包含了AC自动机的核心结构，包括各节点的跳转链、失败函数、权值维护等。

add函数：将字符串添加到AC自动机中，构建跳转链。

build函数：构建完整的跳转链和失败函数。

update函数：更新节点的权值，并在多集合中进行插入和删除操作。

ask函数：查询最大权值，通过跳转链遍历所有可能的节点，取最大值。

代码示例

以上代码示例展示了如何实现上述思路。在实际应用中，可以根据具体需求调整参数和数据结构，确保算法的高效性和正确性。

转载地址：http://hskv.baihongyu.com/

你可能感兴趣的文章