AC 自动机入门

发现了一种 AC 自动机的科学讲法，能够更准确地描述自动机中的数学模型和代码中的对象之间的关系。

字典树模型

假设有$m$个字符串$s_1, \ldots, s_m$，字符集为$\Sigma$，这些字符串构成的字典树为$T = (Q_T, \delta_T)$。其中$Q_T$表示字典树的所有状态，即所有的结点，而$\delta_T: Q_T\times \Sigma \to Q_T$表示字典树的转移函数，即转移边。

考虑到任意$q \in Q_T$都唯一对应一个字符串，我们也认为$Q_T$是一个字符串集合。

AC 自动机模型

对$T$构建的 AC 自动机可以表示为$A = (Q_A, \delta_A)$。

任意$q_T \in Q_T$，与$q_A \in Q_A$唯一对应，$q_A$定义为$Q_T$中所有$q_T$的后缀（包括$q_T$）形成的字符串集合。也就是说$Q_A$是一个字符串集簇。不妨记这个双射为$\sigma: Q_T \to Q_A$，$\sigma q_T = q_A$。

$\delta_A: Q_A\times \Sigma \to Q_A$是 AC 自动机的转移函数。对于$q \in Q_A$，$c \in \Sigma$，假设$q = \{ s_1, \ldots, s_t \}$（$s_i \in Q_T$且$s_i$是$s_{i + 1}$的后缀）。若存在最大的$k$使得$\delta_T(s_k, c)$存在，那么$\delta_A(q, c) \triangleq \sigma\delta_T(s_k, c)$（否则不定义$\delta_A(q, c)$）。

要求出$\delta_A$，我们需要一个辅助函数$f: Q_T\to Q_T$。对于$\sigma s_t = \{ s_1, \ldots, s_t \} \in Q_A$，$f(s_t) \triangleq s_{t - 1}$。这也是所谓的失配指针。有了$f$，我们就可以观察到$q$。

引理 1：设$\sigma \delta_T(s, c) = \{s_1c, s_2c, \ldots, s_tc\}$（$s_t = s$），那么$\{s_1, \ldots, s_t\} \subseteq \sigma s$。

证明：不是所有的$\hat{s} \in \sigma s$都存在$\delta_T(\hat{s}, c)$。

断言 1：$\forall c\in \Sigma, s \in Q_T$，若$\delta_T(s, c)$存在，那么$\sigma f(\delta_T(s, c)) = \delta_A(f( s), c)$。

证明：由引理 1，可以发现$\sigma f( \delta_T(s, c))$末尾去掉$c$得到的集合$\subseteq \sigma f(s)$。结合$\delta_A$的定义，在$\sigma f(s)$中最大的$k$使得$\delta_T(s_k, c)$存在，一定也是$\sigma f(\delta_T(s, c))$中最大的$k$，那么一定有$\delta_T(s_k, c) = f(\delta_T(s, c))$。

断言 2：$\forall c\in \Sigma$：

$$\delta_A(\sigma s, c) = \begin{cases} \delta_T(s, c) & \text{If exists}\\ \delta_A(\sigma f(s), c) & \text{Otherwise} \end{cases}$$

证明：由$\delta_A$定义和$f$定义。

根据上述断言可以得出 AC 自动机的代码实现：

struct AC {
  int tr[SZ][ALP], fail[SZ], tot;
  void init() { tot = -1, new_node(); }
  int new_node() { return ++tot, fail[tot] = 0, memset(tr[tot], 0, sizeof(tr[tot])), tot; }
  void insert(const char *s) {
    for(int u = 0; *s; ++s){
      int c = *s - 'a';
      if (!tr[u][c]) tr[u][c] = new_node();
      u = tr[u][c];
    }
  }
  int q[SZ], ql, qr; // q里就是BFS序
  void build() {
    ql = 1, qr = 0;
    FOR(i, 0, ALP - 1) if (tr[0][i]) q[++qr] = tr[0][i];
    while (ql <= qr) {
      int u = q[ql++];
      FOR(c, 0, ALP - 1) {
        if (tr[u][c]) fail[tr[u][c]] = tr[fail[u]][c], q[++qr] = tr[u][c];
        else tr[u][c] = tr[fail[u]][c];
      }
    }
  }
};