字符串与自动机

高级的字符串算法几乎都与一个重要的概念：确定有限状态自动机（DFA）有关。这是一种重要的数学模型。

概述

这里只讲一些概念，但是非常有用。

OI 中的自动机一般指确定有限状态自动机（DFA）。自动机是一个对信号序列进行判定的数学模型。“信号序列”指的是一连串有顺序的信号，比如字符串从前到后的每一个字符。“判定”是对命题做出真假回答，比如判断一个字符串是否是回文串。

一个 DFA 可以被抽象成一张有向图，由五元组 $(\Sigma, Q, s, F, \delta)$ 构成：

1. 字符集 $\Sigma$，该自动机只能输入这些字符；
2. 状态集合 $Q$，状态相当于图上的顶点；
3. 起始状态 $s$（也可以记作 $start$），$start\in Q$；
4. 接受状态集合 $F$，$F\subseteq Q$；
5. 转移函数 $\delta$，$\delta$ 接受一个状态和一个字符，返回一个状态，转移函数相当于有向图上的边，边的权值是字符。

DFA 可以识别字符串。自动机 $A$ 如果能识别 $S$，那么 $A(S)=True$。DFA 读入字符串时，从初始状态起按照转移函数一个一个字符地转移。如果杜曼一个字符串地所有字符后到达了 $F$ 中的一个点，那么 DFA 就识别了这个字符串。

比如说 Trie 就是一个自动机，每一条边都是转移函数，$F$ 是标记为字符串的节点集合。

KMP 自动机

KMP 自动机的状态集合 $Q$ 为 $0\sim |S|$，如果当前识别的字符串为 $t$，那么每个节点 $i$ 表示已经输入的所有字符 $t[1\dots p]$ 与 $s$ 的最大匹配长度为 $i$，即满足 $s[p-i+1,p]=s[1,i]$，转移函数为：

$$\delta(i, c) = \begin{cases} i+1 ,& s_{i + 1} = c, \\ 0 ,& s_{i + 1} \neq c \land i = 0, \\ \delta(nxt_i, c) ,& s_{i + 1} \neq c \land i \neq 0. \\ \end{cases}$$

int tr[1005][26];
for (int i = 0; i <= n; ++i)
    for (int j = 0; j < 26; ++j) {
        if (i < n && s[i + 1] == j + 'a') tr[i][j] = i + 1;
        else if (i) tr[i][j] = tr[nxt[i]][j];
    }

AC 自动机（ACAM）

它用于解决多模式串

后缀自动机（SAM）

回文自动机（PAM）