KMP & ACAM

· · 算法·理论

KMP

问题 1 定义前缀函数 \pi[i] 为前缀 S[:i] 最长 border。求出 \pi[1] \sim \pi[n]。

连边 i \to \pi[i] 形成 fail 树。fail 树刻画了所有 border 形成的树形结构。

扫描 i = 1\to n,在 fail 树上暴力挂叶子。直接跳右根链,判定当前字符能否接在某个 border 后面。复杂度均摊线性。

:::::info[代码]

for (int i = 2, j = 0; i <= n; i++) {
    while (j && s[i] != s[j+1]) j = pi[j];
    if (s[i] == s[j+1]) j++;
    pi[i] = j;
}

:::::

问题 2 给定字符串 S,构造 DFA,接受且仅接受以 S 为后缀的串。

取最长匹配长度 i 为状态,转移函数

\delta(i,c)= \left\{\begin{matrix} i+1 & i<n\land S[i+1]=c\\ 0 & i=0 \land S[1] \ne c \\ \delta(\pi(i),c) & \text{otherwise.} \end{matrix} \right.

接受状态为 n。节点数 O(n),转移数 O(n |\Sigma|),称作 KMP 自动机。

问题 3 给定文本串 T 和模式串 S,求 S 在 T 中所有出现位置。

对 S 建立 KMP 自动机,输入 T 逐位转移,走到 |S| 则匹配成功,退回 \pi[n] 继续找。

实际上可以避免显式建自动机做到 O(n)。

问题 4(P5829)给定字符串 S,进行 q 次询问,给定 x,y,求 S[:x] 和 S[:y] 的最长公共 border。

所有 border 形成树形结构。建 fail 树 i \to \pi[i],所求转化为 x,y 的 LCA。

ACAM

问题 1 给定字符串 S_1 \sim S_n,构造 DFA,接受且仅接受以某个 S_i 为后缀的串。

对 S_1 \sim S_n 建出 Trie,将 KMP 自动机上树。

定义节点 fail 指针为,当前串的最长真后缀,并且这个后缀对应 Trie 上某个点。转移函数

\delta(i,c)= \left\{\begin{matrix} v & v=\text{son}(u,c) \text{ exists.}\\ \delta(\text{fail}(u),c) & \text{otherwise.} \end{matrix}\right.

特别地,根节点失配的转移边是自环。

构造 ACAM 可以在 Trie 上 BFS。对队首节点 u 枚举转移边 c:

注 上述过程实际上对 fail 链进行了压缩。最原始的构造方法参见 OI Wiki。

取 Trie 中所有模式串结尾的节点集合 E,接受状态为 \{u \mid \exists k \ge 0, \text{fail}^k(u) \in E\}。

节点数 O(L),转移数 O(L |\Sigma|),称作 AC 自动机 / ACAM。

:::::info[代码]

struct ACAM {
    struct node {
        int to[26], fail;
    } T[N];
    int tot = 0;
    void insert(const string& s, int id) {
        int u = 0;
        for (char c : s) {
            int& v = T[u].to[c-'a'];
            if (!v) v = ++tot;
            u = v;
        }
    } 
    void build() {
        queue<int> Q;
        for (int c = 0; c < 26; c++) 
            if (T[0].to[c]) Q.emplace(T[0].to[c]);
        while (!Q.empty()) {
            int u = Q.front(); Q.pop();
            for (int c = 0; c < 26; c++) {
                int& v = T[u].to[c];
                int x = T[T[u].fail].to[c];
                if (!v) {v = x; continue;}
                T[v].fail = x, Q.emplace(v);
            }
        }
    }
} AC;

:::::

问题 2(P3808)给定模式串 S_1 \sim S_n 和文本串 T,求在 T 中出现的文本串数目。

对 S_1 \sim S_n 构造 ACAM,输入 T 逐位转移。考察每个走到的节点 u,向上跳 fail 链找 E 中节点,计入 \text{cnt} 的贡献并标记去重。

跳 fail 链的过程中,遇到被标记点就终止循环,复杂度可以均摊到 O(L)。

问题 3(P5357)给定模式串 S_1 \sim S_n 和文本串 T,对每个 i 求出 S_i 在 T 中出现次数。

对 S_1 \sim S_n 构造 ACAM,输入 T 逐位转移。考察每个走到的节点 u,向上跳 fail 链令 \text{ans}_i \gets \text{ans}_i+1。复杂度 O(L^2)。

连边 u \to \text{fail}(u) 形成 fail 树。转移 T 只求出每个点被经过的次数,最后再对 fail 树做前缀和即可优化到 O(L)。代码。