【学习笔记】ACAM（有图哟~）

Tomwsc · 2026-02-14 10:29:37 · 算法·理论

前言

书接上回，学习字符串实在太过于痛苦，未尝深刻理解。故作此文，用以加深印象。

同时，在这里给大家道歉，由于本人太菜，刷题量很少，所以例题放得太简单了！请各位谅解。

\text{ACAM}

前置知识：\text{Trie}、\text{KMP}（其实不会也无大碍）。

• f_{i,j,1}\leftarrow f_{i-1,fa_j,1}+f_{i-1,fa_j,0}\times [j\ \text{is}\ \text{an}\ \text{endposition}]

注意，这里的 \text{endposition} 需要在 build 时预处理出来，因为若 j 的 \text{fail} 指针指向的状态包含 s_i，则说明 j 也包含 s_i。

:::success[Code]

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

using ll = long long;
using ld = long double;
using ull = unsigned long long;
using i128 = __int128;

using PII = pair<int, int>;
using PLL = pair<ll, ll>;

constexpr ll inf = (1ll << 62);
constexpr int N = 2e5 + 10;

int n, m;

struct acam {
    int tot = 0, mod;
    struct Trie {
        int son[26], fail, flag;
    };
    vector<Trie> trie;

    acam(int _n, int _mod) : mod(_mod) {
        trie.resize(_n);
    }

    int get(char c) {
        return c - 'A';
    }

    void insert(string s) {
        int p = 0;
        for (auto i : s) {
            int x = get(i);
            if (!trie[p].son[x]) {
                trie[p].son[x] = ++tot;
            }
            p = trie[p].son[x];
        }
        trie[p].flag = 1;
    }

    void build() {
        queue<int> q;
        for (int i = 0; i < 26; i++) {
            if (trie[0].son[i]) {
                trie[trie[0].son[i]].fail = 0;
                q.push(trie[0].son[i]);
            }
        }
        while (!q.empty()) {
            int u = q.front();
            q.pop();
            for (int i = 0; i < 26; i++) {
                if (!trie[u].son[i]) trie[u].son[i] = trie[trie[u].fail].son[i];
                else {
                    trie[trie[u].son[i]].fail = trie[trie[u].fail].son[i];
                    trie[trie[u].son[i]].flag |= trie[trie[trie[u].son[i]].fail].flag;
                    q.push(trie[u].son[i]);
                }
            }
        }
    }

    void add(ll& x, ll y) {
        x += y;
        if (x >= mod) {
            x -= mod;
        }
    }

    ll calc(int len) {
        vector<vector<array<ll, 2>>> f(tot + 1);
        for (int i = 0; i <= tot; i++) {
            f[i].resize(len + 1);
        }
        for (int i = 0; i < 26; i++) {
            if (trie[trie[0].son[i]].flag) {
                add(f[trie[0].son[i]][1][1], 1);
            } else {
                add(f[trie[0].son[i]][1][0], 1);
            }
        }
        for (int i = 1; i < len; i++) {
            for (int j = 0; j <= tot; j++) {
                for (int k = 0; k < 26; k++) {
                    if (trie[trie[j].son[k]].flag) {
                        add(f[trie[j].son[k]][i + 1][1], f[j][i][0]);
                        add(f[trie[j].son[k]][i + 1][1], f[j][i][1]);
                    } else {
                        add(f[trie[j].son[k]][i + 1][1], f[j][i][1]);
                        add(f[trie[j].son[k]][i + 1][0], f[j][i][0]);
                    }
                }
            }
        }
        ll ans = 0;
        for (int i = 0; i <= tot; i++) {
            add(ans, f[i][len][1]);
        }
        return ans;
    }
};

void solve() {
    cin >> n >> m;
    acam ac(N, 1e4 + 7);
    for (int i = 0; i < n; i++) {
        string s;
        cin >> s;
        ac.insert(s);
    }
    ac.build();
    cout << ac.calc(m) << "\n";
}

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

;;; ::::

CF696D

::::info[题意]{open} 给定 n 个字符串 s_{1\dots n} 和其价值 a_{1\dots n}。求长度不超过 l 的字符串 t 的最大价值是多少。

• :::: ::::success[做法] 如果 $l$ 的值域很小，则可以直接暴力 $\text{ACAM}$ 上 $\text{dp}$。但 $l$ 取到了 $10^{14}$，所以得考虑如何进行优化。

不妨先把状态和转移方程写出来。设 f_{u, i} 表示走到 \text{ACAM} 上的点 u 且当前处理的字符串长度为 i 的最大答案。转移就是刷表，w_u 是贡献，可以在建 \text{ACAM} 时顺便处理 \text{fail} 指针算出来：

观察到，这个转移式其实等同于从 fa_u 向 u 走过了一条边权为 w_u 的边。而求长度不超过 l 的字符串其实就相当于在 \text{ACAM} 上从根节点开始走 l 步。由此联想到邻接矩阵加矩阵快速幂。但此时应使用广义矩阵乘，每次计算的是 c_{i,j}=\max\{a_{i,k}+b_{k,j}\}。

时间复杂度为 O(n^3\log l)。

:::success[Code]

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

using ll = long long;
using ld = long double;
using ull = unsigned long long;
using i128 = __int128;

using PII = pair<int, int>;
using PLL = pair<ll, ll>;

constexpr ll inf = (1ll << 62);
constexpr int N = 2e5 + 10;

template <typename T> void chkmax(T& a, T b) { a = max(a, b); }
template <typename T> void chkmin(T& a, T b) { a = min(a, b); }

template <typename T>
struct Matrix {
    int n;
    vector<vector<T>> mat;

    Matrix(int _n) : n(_n) {
        mat.resize(n + 1, vector<T> (n + 1));
        for (int i = 0; i <= n; i++) {
            mat[i][i] = 1;
        }
    }

    Matrix(int _n, T flag) : n(_n) {
        mat.resize(n + 1, vector<T> (n + 1, flag));
    }

    Matrix operator*(const Matrix& a) {
        Matrix<T> c(n, -1);
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= n; j++) {
                for (int k = 0; k <= n; k++) {
                    if (mat[i][k] < 0 || a.mat[k][j] < 0) continue;
                    // cout << i << " " << k << " " << mat[i][k] << " 1\n";
                    // cout << k << " " << j << " " << a.mat[k][j] << " 2\n";
                    chkmax(c.mat[i][j], mat[i][k] + a.mat[k][j]);
                }
            }
        }
        return c;
    }

    Matrix qpow(ll x) const {
        Matrix<T> base = *this;
        Matrix<T> res = base;
        x--;
        while (x) {
            if (x & 1) res = res * base;
            x >>= 1;
            base = base * base;
        }
        return res;
    }
};

template <typename T>
struct ACAM {
    int tot = 0;
    struct Trie {
        int son[26], fail, ans;

        Trie() : fail(0), ans(0) {
            memset(son, 0, sizeof(son));
        }
    };
    vector<Trie> trie;
    vector<int> a;

    ACAM(int _n) {
        trie.resize(_n + 1);
        a.resize(_n + 1);
    }

    int get(char c) {
        return c - 'a';
    }

    void insert(string s, int id) {
        int p = 0;
        for (auto i : s) {
            int x = get(i);
            if (!trie[p].son[x]) {
                trie[p].son[x] = ++tot;
            }
            p = trie[p].son[x];
        }
        trie[p].ans += a[id];
    }

    void build() {
        queue<int> q;
        for (int i = 0; i < 26; i++) {
            if (trie[0].son[i]) {
                trie[trie[0].son[i]].fail = 0;
                q.push(trie[0].son[i]);
            }
        }
        while (!q.empty()) {
            int u = q.front();
            q.pop();
            for (int i = 0; i < 26; i++) {
                if (!trie[u].son[i]) trie[u].son[i] = trie[trie[u].fail].son[i];
                else {
                    trie[trie[u].son[i]].fail = trie[trie[u].fail].son[i];
                    trie[trie[u].son[i]].ans += trie[trie[trie[u].son[i]].fail].ans;
                    q.push(trie[u].son[i]);
                }
            }
        }
    }

    T calc(ll l) {
        Matrix<T> mapp(tot, -1);
        for (int i = 0; i <= tot; i++) {
            for (int j = 0; j < 26; j++) {
                mapp.mat[i][trie[i].son[j]] = trie[trie[i].son[j]].ans;
            }
        }
        mapp = mapp.qpow(l);
        T ans = 0;
        for (int i = 0; i <= tot; i++) {
            chkmax(ans, mapp.mat[0][i]);
        }
        return ans;
    }
};

void solve() {
    int n;
    ll l;
    cin >> n >> l;
    ACAM<ll> ac(210);
    for (int i = 1; i <= n; i++) {
        cin >> ac.a[i];
    }
    for (int i = 1; i <= n; i++) {
        string s;
        cin >> s;
        ac.insert(s, i);
    }
    ac.build();
    cout << ac.calc(l) << "\n";
}

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

::: ::::

后记

给两个题单：一、二。第一个是我自己做过的一些简单 \text{ACAM}，拜谢 fjy666。

真的爆肝了数天啊，给个赞吧！