2024.12.16 自动机理论 & 常见自动机 讲课笔记

szt100309 · 2024-12-17 20:22:08 · 个人记录

自动机理论

严格来说，自动机不是算法或数据结构，只是一种数学模型

符号 和 基本定义

对于 \text{DFA}\,\, M=(\sum,Q,q_0,F,\delta)，令所有 M 可以接受的字符串的集合为 L(M)，则称 M 可以识别语言 L(M)

若一个语言可以被 \text{DFA} 识别，则其为正则语言

若将状态看为点，转移函数看为边，则可以把一个 \text{DFA} 画为一张状态图，其中用一个箭头指向 q_0，用同心圆标出所有 F 中元素

非确定有限状态自动机（NFA）

一个 \text{NFA} 定义为一个五元组 (\sum,Q,q_0,F,\delta)，其中前四项与 \text{DFA} 相同，第五项 \delta:Q\times\sum\rightarrow 2^Q 为转移函数，接受参数为一个二元组，返回一个状态的集合

对于字符串 s=s_1s_2\cdots s_n 和 \text{NFA} (\sum,Q,q_0,F,\delta)，若 \exists r_0,r_1,\cdots,r_n，使得 q_0=r_0,\forall 1\le i\le n(r_i\in \delta (r_{i-1},s_i)),r_n\in F，则称该自动机可以接受 s

对于 \text{NFA}\,\, M=(\sum,Q,q_0,F,\delta)，令所有 M 可以接受的字符串的集合为 L(M)，则称 M 可以识别语言 L(M)

对于每个块，枚举 2^T 个子集 和 |\sum| 个字符，处理出每个子集在各种字符下的转移，这部分时间复杂度为 O\left(2^T|\sum|\cdot\dfrac{|Q|}T\cdot \dfrac{|Q|}\omega\right)=O\left(\dfrac{|Q|^22^T|\sum|}{T\omega}\right)

转移时，直接将 \dfrac{|Q|}T 个块的预处理结果拼起来即可，这部分时间复杂度 O\left(|S|\cdot\dfrac{|Q|}T\cdot\dfrac{|Q|}\omega\right)=O\left(\dfrac{|S||Q|^2}{T\omega}\right)

总时间复杂度 O\left(\dfrac{|Q|^22^T|\sum|}{T\omega}+\dfrac{|S||Q|^2}{T\omega}\right)，令 T=\log\dfrac{|S|}{|\sum|}，则时间复杂度为 O\left(\dfrac{|S||Q|^2}{\omega\log\frac{|S|}{|\sum|}}\right)

DFA 最小化

将 \text{DFA} 转化为与其等价的 \text{DFA} 中状态数最少的一个

使用 Hopcroft 算法

首先去除无法从 q_0 到达和无法到达 F 的状态

定义两个状态 u 和 v 无法区分当且仅当 [u\in F]=[v\in F] 且两者所有转移对应相同或无法区分

先将所有状态按是否被接受划分为两个等价类

每次取出一个等价类 S，使得存在 u,v\in S，满组存在 c\in\sum，使得 \delta(u,c)\ne \delta(v,c)。将 S 按 \delta(s,c)\;(s\in S) 是否与 \delta(u,c) 相同分为两个等价类。直到不存在满足要求的等价类为止

最后将每个等价类作为新 \text{DFA} 的一个状态即可，可证这样是最小的

此算法可以进一步优化

维护一个还没有被考虑过的等价类的集合 W

每次从 W 中取出一个 X，枚举 c\in\sum，对于所有 \exists u\in Y,\delta(u,c)\in X 的 Y（建反图找），若其可以划分，则将 Y 分裂为 A 和 B。若 Y 没被考虑过，则将 A 和 B 放入 W。否则将较小的一个放入 W

这样时间复杂度为 O(|\sum||Q|\log|Q|)

例 1：CF1142D Foreigner

定义正整数 n 合法当且仅当 1\le n\le 9，或 \lfloor\frac n{10}\rfloor 合法且 n 的个位数严格小于 n 在所有合法正整数中的排名（从 1 开始）\bmod 11。给定字符串 s\;('0'\le s_i\le'9',s_1\ne'0')，求其合法子串数量（不能有前导 0）。|s|\le10^5

定义一个合法正整数 x 生成另一个合法正整数 y 当且仅当 x=\left\lfloor\frac y{10}\right\rfloor

根据题意，若合法正整数 x 排名为 k，则其可以生成 10x\sim 10x+(k\bmod 11)-1

对于一个 x，显然它排在 [1,\left\lfloor\frac x{10}\right\rfloor-1] 内合法的数及其生成的数 和 \left\lfloor\frac x{10}\right\rfloor 生成的小于 x 的数 之后

前者一共 9+\sum_{i=1}^{k-1}(i\bmod 11) 个（其中 k 为 \left\lfloor\frac x{10}\right\rfloor 的排名），后者共 c 个（其中 c 为 x 的个位）

因此 x 的排名为 9+\sum_{i=1}^{k-1}(i\bmod 11)+c+1

由于 0+1+\cdots+10\equiv0\pmod{11}，可构造 DFA：

• \sum=[0,9]\cap\Bbb Z
• F=[0,10]\cap\Bbb Z
• Q=\{s\}\cup F
• q_0=s
• \delta(u,c)=\begin{cases}c&u=s,c\ne0\\(10+\sum_{i=0}^{u-1}i+c)&u\ne s,c<u\bmod11\end{cases}

其中状态 x（\ne s）的意义为当前前缀对应的合法正整数排名 \bmod11

容易根据转移写出 dp 方程（注意可以从任意下标进入 DFA，s 状态不一定要是 1 下标）

代码

例 2：P4590 [TJOI2018] 游园会

给定长为 k 的字符串 t，对于每个 0\le i\le k，求长为 n 的字符串 s 的数量，满足两者的 LCS 等于 i，且该字符串不含子串 NOI。两者的字符集都是 \{N,O,I\}。n\le1000,k\le15

令 dp_{i,j,s} 为长为 i 的字符串，其仅有长为 j 的后缀和 NOI 的后缀匹配 时的方案数，其中 s 描述了一个关于 s[1:i] 和 t 的匹配情况的 DFA 上的状态，每次在后面加 N,O,I 中某个字符，其转移到的 dp 位置的 i 下标加一，j 由加入字符和原先匹配长度确定，s 则是原本 s 加入该字符后新走一步的状态

令 s 为长为 k 的二进制数，每一位分别表示 t 的对应位有没有和 s 匹配（必须为极大匹配），转移时将其转化为长为 k 的数组，每个位置表示 t 的当前前缀和 s 的 LCS，用新加入的字符跟新其状态，然后再将其压缩为长为 k 的二进制数

这种技巧也被称为 dp 套 dp，因为 s 的转移本身就是一个 dp，一般来说内层的 dp 状态都较小。若内层 dp 状态过大，则需要使用 DFA 最小化算法减少状态数（若状态是静态的则手算，否则需要在运算过程中动态执行 Hopcroft）

总时间复杂度 O(nk2^k)，常数较大，应该可以优化到 O(k2^k+n2^k)

代码

子序列自动机

接受且仅接受给定序列的子序列的自动机

模板：

#include <bits/stdc++.h>

//subsequence automaton
namespace SsAM {
    struct SsAM {
        static constexpr std::size_t MAX_LENGTH = 100010;
        std::size_t nx[MAX_LENGTH][26], __n;
        void build(const std::string &_s, std::size_t _n){//_s begin at 1
            __n = _n; static std::size_t last_pos[26]; std::fill_n(last_pos, 26, 0);
            for (std::size_t i = _n; ~i; --i)std::copy_n(last_pos, 26, nx[i]), last_pos[_s[i] - 'a'] = i;
        }
        std::size_t delta(std::size_t _Nw, char _ch) const { return nx[_Nw][_ch - 'a']; }
        bool is_subsq(const std::string &s) const//s begin at 0
        { std::size_t nw = 0; for (const char &c : s){ nw = delta(nw, c); if (!nw)return false; } return true; }
    };
}

KMP 自动机（KMPAM）

将原本均摊 O(1) 的 KMP 做到严格 O(1)

模板题：CF1721E Prefix Function Queries \quad 代码

模板：

#include <bits/stdc++.h>

namespace KMPAM {
    struct KMPAM {
        static constexpr std::size_t MAX_LENGTH = 100010;
        std::size_t nxt[MAX_LENGTH][26], pi[MAX_LENGTH], __n;
        std::string __s;
        void build(const std::string &s, std::size_t n){
            if (!n)return;pi[0] = pi[1] = 0;std::fill_n(nxt[0], 26, 0); __n = n; __s = s;
            for (std::size_t i = 1; i <= n; ++i){
                if (i > 1){
                    pi[i] = pi[i - 1];
                    while (pi[i] && s[pi[i] + 1] ^ s[i]){
                        if (pi[i] + 1 < i){pi[i] = nxt[pi[i]][s[i] - 'a'];break;}
                        pi[i] = pi[pi[i]];
                    }
                    pi[i] += s[pi[i] + 1] == s[i];
                }
                for (std::size_t c = 0; c < 26; ++c)nxt[i][c] = nxt[pi[i]][c];if (i < n)nxt[i][s[i + 1] - 'a'] = i;
            }
        }
        std::size_t delta(std::size_t nw, char c){ return nxt[nw][c - 'a']; }
        void append(const std::string &t){
            if (!t.size())return;
            __s += t; std::size_t m = t.size();
            for (std::size_t c = 0; c < 26; ++c)nxt[__n][c] = nxt[pi[__n]][c];
            nxt[__n][__s[__n + 1] - 'a'] = __n;
            for (std::size_t i = __n + 1; i <= __n + m; ++i){
                pi[i] = pi[i - 1];
                while (pi[i] && __s[pi[i] + 1] ^ __s[i]){
                    if (pi[i] + 1 < i){pi[i] = nxt[pi[i]][__s[i] - 'a'];break;}
                    pi[i] = pi[pi[i]];
                }
                pi[i] += __s[pi[i] + 1] == __s[i];
                for (std::size_t c = 0; c < 26; ++c)nxt[i][c] = nxt[pi[i]][c];if (i < __n + m)nxt[i][__s[i + 1] - 'a'] = i;
            }
            __n += m;
        }
        void resize(std::size_t _N){ __n = _N; __s.resize(_N + 1); }
    };
}

AC 自动机（ACAM）

模板题：P5357 【模板】AC 自动机

模板：

#include <bits/stdc++.h>

namespace ACAM {
    struct ACAM {
        typedef std::size_t size_t;
        static constexpr std::size_t MAX_LENGTH = 200010;
        size_t trie[MAX_LENGTH][26], tot, fail[MAX_LENGTH], deg[MAX_LENGTH];
        ACAM():tot(0){
            std::fill_n(*trie, sizeof(trie) / sizeof(**trie), 0);
            std::fill_n(fail, sizeof(fail) / sizeof(*fail), 0);
            std::fill_n(deg, sizeof(deg) / sizeof(*deg), 0);
        }
        size_t insert(const std::string &_s)//begin at 0
        { size_t nw = 0; for (const char &c : _s){ size_t &_nx = trie[nw][c - 'a']; if (!_nx)_nx = ++tot; nw = _nx; } return nw; }
        void build(){
            std::queue<size_t> _q; for (const size_t &i : trie[0])if (i)_q.emplace(i);
            while (!_q.empty()){
                size_t _t = _q.front(); _q.pop();
                for (size_t i = 0; i < 26; ++i)
                    if (trie[_t][i])++deg[fail[trie[_t][i]] = trie[fail[_t]][i]], _q.emplace(trie[_t][i]);
                    else trie[_t][i] = trie[fail[_t]][i];
            }
        }
        size_t delta(size_t nw, char _ch) const { return trie[nw][_ch - 'a']; }
        std::vector<size_t> get_match_count(const std::vector<std::string> _v, const std::string &_s){
            size_t __cnt = 0; std::vector<size_t> edps(_v.size());
            for (const std::string &_s : _v) edps[__cnt++] = insert(_s);
            build(); std::vector<size_t> __tmp(tot + 1);
            size_t nw = 0; for (const char &_c : _s)++__tmp[nw = delta(nw, _c)];
            std::queue<size_t> _q; for (size_t i = 0; i <= tot; ++i)if (!deg[i])_q.emplace(i);
            while (!_q.empty()){
                size_t _t = _q.front(); _q.pop(); __tmp[fail[_t]] += __tmp[_t];
                if (!--deg[fail[_t]])_q.emplace(fail[_t]);
            }
            std::vector<size_t> ret(_v.size());
            for (size_t _i = 0, _ = _v.size(); _i < _; ++_i)ret[_i] = __tmp[edps[_i]]; return ret;
        }
    };
}//passed P5357

其常用于多模式字符串匹配

例 1：QOJ # 6842. Popcount Words

令 s_i=\operatorname{popcount}(i)\bmod 2\;(i\in\Bbb N)，给定 (l_i,r_i)\;(1\le i\le n)，令 S=s[l_1,r_1]+s[l_2,r_2]+\cdots+s[l_n,r_n]，给定 q 个询问，每次给定一个 0/1 字符串 t_i，查询其在 S 中匹配次数，l_i,r_i\le10^9,n,q\le10^5,\sum_i|t_i|\le5\times10^5

将所有询问离线并建出 AC 自动机，则问题转化为给定的 S 在 AC 自动机上转移，求每个节点被覆盖到的次数（最终某个字符串的答案即为其对应节点的子树中的总覆盖次数）

实际上 S 为 Thue-Morse 序列

定义 S 长为 2 的幂次的前缀为合法前缀，定义字符串的翻转为将 0 和 1 互换，则 S 的每个区间可以分为 O(\log V) 个连续子段，满足每一段都是 S 的合法前缀或合法前缀的翻转（具体拆分方法见代码）

因此可以将 S 转化为 O(n\log V) 段合法前缀和合法前缀的翻转

令 to_{i,j,0/1} 表示从 AC 自动机的节点 j 出发，用 S 长为 2^i 的前缀 / 前缀的翻转转移所能达到的节点，容易通过倍增 O(n\log V) 预处理

最后所有覆盖次数都存在 g_{0,j,0/1} 中，用 to 直接加到对应节点的次数上即可

总时间复杂度 O(n\log V)

代码

例 2：P8147 [JRKSJ R4] Salieri

给定 n 个字符串，每个字符串 s_i 有权值 v_i，给定 m 组 (S,k)，分别求出可重集 \{cnt_i\times v_i\mid1\le i\le n\} 的第 k 大值，其中 cnt_i 表示 s_i 在 S 中出现次数，n,m\le10^5,\sum|s_i|\le5\times10^5,\sum|S|\le5\times10^5

先用 s_i 建出 AC 自动机

用 S 在 AC 自动机上转移，则 cnt_i 就是子树 i 内节点被经过的次数和

二分答案，转化为求 cnt_i\times v_i\ge k 的数量

对 t 建立 AC 自动机，问题等价于对于 S 每个前缀转移到的节点，以其为起点开始随机游走，走到 n 个被标记点（t_i 结尾处）的期望步数（若在 S 前缀转移过程中已经到达某个被标记点，则之后的答案都为前缀本身的长度，这一点需要特判）

直接高斯消元有 O(nm) 个未知量，考虑优化

在 AC 自动机的 Trie 上从根开始 bfs，根本身必然为未知量

当处理到某个标记节点时，相当于新得到一个方程

处理非标记节点时，则选择其一个儿子为重儿子，其余轻儿子全部设为未知量，重儿子的答案可以用其父亲、其父亲的亲儿子、其父亲非儿子转移节点（显然它们深度更小，此时其表示已被求出）表示出

总未知量数量为轻儿子总数加一，等于 n，方程数量也是 n（对于多个 t 相同的情况，仅保留其中一个，其余删除即可）

于是可以高斯消元 O(n^3) 求解

然后回带即可求出每个节点的答案

总时间复杂度 O(n^3+n^2m+|S|)

代码

回文树 / 回文自动机（PAM）

维护某个序列所有回文子串的结构，严格来说不是自动机，但形式相近

模板题：P5496 【模板】回文自动机（PAM）

模板：

#include <bits/stdc++.h>

namespace PAM {
    struct PAM {
        typedef std::size_t size_t;
        static constexpr size_t MAX_LENGTH = 500010;
        std::string __s; size_t __lst;
        size_t tot, nx[MAX_LENGTH][26], Ln[MAX_LENGTH], fail[MAX_LENGTH], hlf[MAX_LENGTH], __f[MAX_LENGTH];
        //str hlf[x] is the longest str that str hlf[x] is str x's suffix and len(hlf[x])<=len(x)/2
        size_t _tot[MAX_LENGTH], _cnt[MAX_LENGTH];
        size_t __i;
        PAM():tot(1), __s("."), __i(0){
            std::fill_n(*nx, sizeof(nx) / sizeof(**nx), 0);
            std::fill_n(Ln, MAX_LENGTH, 0);
            std::fill_n(fail, MAX_LENGTH, 0);
            std::fill_n(hlf, MAX_LENGTH, 0);
            std::fill_n(_tot, MAX_LENGTH, 0);
            std::fill_n(_cnt, MAX_LENGTH, 0);
            fail[0] = 1;Ln[1] = -1;hlf[1] = 1;__i = 0;__lst = 0;
        }
        size_t _get_fail(size_t __nw)
        {while (__nw ^ 1 && __s[__i - Ln[__nw] - 1] != __s[__i])__nw = fail[__nw];return __nw;}
        size_t insert(char c){
            __s.push_back(c);++__i;
            size_t nw = _get_fail(__lst);
            if (!nx[nw][c - 'a']){
                Ln[++tot] = Ln[nw] + 2;
                fail[tot] = nx[_get_fail(fail[nw])][c - 'a'];
                _tot[tot] = _tot[fail[tot]] + 1;
                nx[nw][c - 'a'] = tot;
                if (Ln[tot] < 2)hlf[tot] = 0;
                else {
                    int x = hlf[nw];
                    while (x ^ 1 && (Ln[x] + 2 > Ln[tot] >> 1 || !nx[x][c - 'a'] || __s[__i - Ln[x] - 1] ^ __s[__i]))x = fail[x];
                    hlf[tot] = nx[x][c - 'a'];
                }
                __f[tot] = nw;
            }
            ++_cnt[__lst = nx[nw][c - 'a']];
            return _tot[__lst];
        }
        void build(const std::string s){for (const char &c : s)insert(c);}
        size_t delta(size_t nw, char ch){return nx[nw][ch - 'a'];}
    };
}

由其建立过程可知，某个字符串本质不同的回文子串数量不超过其长度

例 1：P4762 [CERC2014] Virus synthesis

一个字符串初始为空，每次可以在其开头或结尾加一个字符，或在其开头或结尾拼接其逆串（以下称此操作为翻转），求构造出给定字符串 S 的最小步数，n=|S|\le 10^5

先对原字符串建立 PAM，考虑在 PAM 上 dp

令 dp_i 表示构造出 PAM 上节点 i 所需的最少步数，len_i 表示节点 i 代表字符串的长度，则最终答案为 \min_{i\mid len_i\equiv0\pmod 2}(n-len_i+dp_i)（显然根据题目的生成过程，翻转得到的一定为长度为偶数的回文串），初始偶根的 dp 值为 0，与偶根直接相连的节点 dp 值为 2

可证对于一个偶回文串，其一定存在一种最优操作方式，满足最后一步为翻转

因此转移有两种（奇回文串不用转移），从父节点转移 和 从其祖先中最长的满足长度不超过其一半的偶串（若不存在则忽略这种转移）转移

前者只要在父节点翻转前在末尾增一个字符即可，dp_i\gets dp_{fa_i}+1

后者需要补足一半的长度然后翻转，令满足要求的节点为 j（可以在建立 PAM 时均摊 O(1) 算出，也可以建好后在链上二分，单次 O(\log n)），则 dp_i\gets dp_j+\frac{len_i}2-len_j+1

总时间复杂度 O(n|\sum|) 或 O(n\log n+n|\sum|)

代码

例 2：bzoj#P3103. Palindromic Equivalence

给定 S，求有多少与其长度相同的 T，满足 S[l:r] 为回文串当且仅当 T[l:r] 为回文串，且 T 仅含 26 个字母，n=|S|\le10^6

在建立 PAM 的过程中，可以得出哪些位置必须相同，哪些必须不同（实际上 Manacher 也可以，代码中用了 Manacher 的方法）

具体地，在 PAM 跳 fail 时，每个节点对应回文串的两端的位置一定相同，fail 上一个回文串的两端对应字符一定不同（否则 fail 就可以少跳一次）（对应到 Manacher，暴力扩展的位置对应相等，扩展到极限的下一组一定不等）

将相同的用并查集合并为一个等价类，不同的等价类之间连边（代码中是将等价类之间的边全部连在等价类中编号最小的点上）

按编号从小到大考虑每个等价类，这个等价类的选择有 26 减与之不同且已经考虑过的等价类数量 种，所有等价类方案数之积即为答案（不需要考虑负数的情况，因为在它之前一定出现过 0 了）

时间复杂度 O(n|\sum|)

代码

例 3：QOJ # 5440. [The 2022 ICPC Asia Shenyang Regional Contest] [The 1st Universal Cup. Stage 1: Shenyang] P-P-Palindrome

给定 s_{1\sim n}，求 (P,Q) 的数量取模（位置不同但字符串相同算一个，P,Q 不同则交换算两个），满足 P,Q,PQ 都是回文串且 P,Q 都为某个 s_i 的子串（可以相交，可以来着不同的 s_i），n,\sum|s_i|\le10^6

对于一组 (P,Q)，若 |P|=|Q| 则 P=Q，若 |P|<|Q| 则 P 为 Q 的回文后缀，否则 Q 为 P 的回文前缀。因此若确定了 P 和 Q 中较长的一个，则较短的一个可以取其满足剩余后缀也是回文串的回文前缀

原问题等价于对 s_{1\sim n} 的每个本质不同的回文子串 S，枚举 1\le i\le |S|，求 prf(S,i) 和 sff(S,i+1) 都是回文串的 (i,S) 的权值和（若 i<n 则权值为 2，因为可以交换两者，否则权值为 1）

若 n>1，则可以将 n 个 s 拼起来，两两之间加入两个相异的字符（且不包括在原本字符串的字符集内），例如程序中用了 '\{','|'（因为在 ASCII 中其为 'z' 接下来两个字符，在 PAM 中减去 'a' 直接映射到 [0,28) 中），最后答案要减去 2，因为把 P=Q='\{' 和 P=Q='|' 计入了答案。以下只考虑一个字符串的情况，记其为 s_0

可证若 S 为回文串，则 (i,S) 合法当且仅当 i 为 S 最小整周期的倍数

对 s_0 建出 PAM，则节点 i 对应字符串的最小整周期长度等于 len_i-len_{fail_i} 当且仅当 (len_i-len_{fail_i})\mid len_i，其他情况其最小整周期等于其自身

答案即为每个节点 i 的 2\cdot\frac{|S_i|}{p_i}-1 之和（由之前贡献计算方式可得），其中 S_i 为节点 i 代表的字符串，p_i 为其最小整周期。注意要对 S_i 去重

另一种统计答案的方式（代码中的方式）为对于 PAM 每个节点，将其最小整周期插入哈希表，则答案为每种最小整周期出现次数的平方和。其正确性为考虑最终哈希表中每组 (S,c)，其中 S 为某字符串的最小整周期，c 为其被累加的次数，则由 PAM 的构建过程可知 s_0 一定存在一个子串等于 S^c，且不存在子串 S^{c+1}，此时 P 和 Q 可以分别取 S^1,S^2,\cdots,s^c（显然 S 为回文串），总共 c^2 种选择

时间复杂度 O(n|\sum|)

代码

例 4：P5433 月宫的符卡序列

给点字符串 S（下标从 0 开始），定义字符串的价值为其在 S 中所有出现位置中点（左右边界之和除以 2 下取整）的异或和，求 S 所有回文子串的最大价值，|S|\le10^6，多测 T\le 5

先求出 S 所有本质不同的回文串，并对每个子串求出一个指针，指向等于它去掉首尾后得到的回文串，长度小于 3 的没有指针（所有指针和节点构成内向森林，其等同于 PAM 的 fail 树去掉奇根和偶根后得到的森林），称这些为根（可能有多个）

每个回文串保存一个值 ps，代表其出现位置中点的异或和

则每个极长回文子段会令其对应节点到根路径上所有点的 ps 异或上该子段的中点

打上标记最后统一上传即可

时间复杂度 O(n)

代码

vjudge 练习

FSM，pw:AstroBot

参考

oi-wiki AC 自动机

oi-wiki 回文树

FSM.pdf by Mine_King

字符串乱学 by Mine_King