自动机学习笔记

自动机，全称有限状态自动机（ $DFA$ ）是信息学中一类常用的算法。

它包括 5 个要素：

状态集合 $Q$
字符集 $\Sigma$
状态转移函数 $\delta$ 使得 $\delta(q, \sigma) = q'(q, q'\in Q, \sigma\in \Sigma)$
开始状态 $s \in Q$
接收的状态集合 $F\subseteq Q$

可以把这个东西看成一张有向图，图中的所有顶点所组成的集合为 $Q$ ，图中的边为 $\delta$ ，边权只能为 $\Sigma$ 中的一种。 $s$ 为起点。

值得一提的是，并不是所有的自动机都是一棵树，但必然是一个 $DAG$ 。

$AC$ 自动机

$AC$ 自动机是一类以 $Trie$ 为基础，结合了 $KMP$ 思想，用来在线性时间内解决多串同时匹配问题的算法。它通过维护 $fail$ 指针来保证复杂度，类似与 $KMP$ 的 $nxt$ 数组，不同的是，它维护的是全局失配转移路径，即有可能在 $A$ 串匹配完成或失败后直接开始进行对 $B$ 串的匹配。

具体实现：

$fail$ 指针的含义：设字符串 $rootAB$ 在 $Trie$ 上路径末尾对应的节点 $a$ ，则 $fail_a$ 指向的便是路径 $rootB$ 的末尾 $b$ ，且满足 $B$ 最大，但并不一定是这条链的结尾。如：一个 $Trie$ 中顺序插入了 $ABC$ , $BCD$ 和 $C$ 则他们的节点编号为 123 456 7 那么 $fail_3 = 5$ .

同时可以得出一个节点 $fail$ 指向的节点深度一定小于当前节点。

$AC$ 自动机的构建：

先把 $Trie$ 树构建出来，然后通过广搜构建 $fail$ 指针。

将第一层所有节点的 $fail$ 指针指向 $root$ ，并将它们入队。

令某个节点父亲节点 $fail$ 指针的相同转移子节点为失配节点。
如果当前节点存在，将它的 $fail$ 指向失配节点。
如果当前节点不存在，将它指向失配节点。

通过这样的操作，根据广搜的特性，深度小于它的节点一定比它先搜到，所以无论失配节点存不存在，这个操作都是有意义的。

通过上面的构造，就打通了一条从当前节点到 $root$ 的路径。也就是说不同于 $KMP$ ，无需判断是否失配直接跳子节点即可。

经典的操作：

查询每个模式串在文本串中出现的次数。
查询出现最多的模式串和出现次数。

查询时每到一个节点将它的标记 $+1$ ，最后将每个点的 $fail$ 向它连边（注意方向），然后跑一边类似树形 DP 的操作，向上统计答案即可，因为如果某个串成功匹配，一定会对它 $fail$ 边指向的节点造成贡献。

一定要反向连边的原因是所有的节点最终都会 $fail$ 到 $root$ ，反向连边方便进行 $dfs$ ，当然也可以进行拓扑排序正向连边，同时统计答案。

代码实现：

// 自动机 学习笔记
// AC 自动机的构建
void build() {
  for (int i = 0; i < 26; i++) {
    if (trie[0][i]) {
      fail[trie[0][i]] = 0;
      q.push(trie[0][i]);
    }
  }
  queue<int> q;
  while (!q.empty()) {
    int x = q.front(); q.pop();
    for (int i = 0; i < 26; ++i) {
      int y = trie[x][i];
      if (y) {
        fail[y] = trie[fail[x]][i];
        q.push(y);
      } else
        trie[x][i] = trie[fail[x]][i];
    }
  }
}

int vis[Maxn];
void search(char* s) {
  int n = strlen(s), p = 0;
  for (int i = 0; i < n; ++i) {
    p = trie[p][s[i] - 'a'];
    vis[p]++;
  }
}

P5357 【模板】AC自动机（二次加强版）

代码实现：

// 自动机 学习笔记
// AC自动机二次加强版 || AC自动机模板
// Code By CloudySky
#include <bits/stdc++.h>
// #define int long long
namespace IO
const int Maxn = 2e6 + 10;
using namespace std;

int trie[Maxn][26], tot;
int v[Maxn], id[Maxn];
void insert(char* s, int cur) {
  int p = 0, n = strlen(s);
  for (int k = 0; k < n; ++k) {
    int ch = s[k] - 'a';
    if (!trie[p][ch])
      trie[p][ch] = ++tot;
    p = trie[p][ch];
  }
  v[p] = cur, id[cur] = p; 
}

int fail[Maxn];

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

int vis[Maxn];

void search (char* s) {
  int n = strlen (s), p = 0;
  for (int i = 0; i < n; ++i) {
    p = trie[p][s[i] - 'a'];
    vis[p] ++;
  }
}

struct edge {
  int v, nxt;
} e[Maxn << 1];
int hd[Maxn], cnt;
void add (int u, int v) {
  e[++cnt] = (edge) {v, hd[u]};
  hd[u] = cnt;
}

void dfs (int x) {
  for (int i = hd[x]; i; i = e[i].nxt) {
    int y = e[i].v;
    dfs (y);
    vis[x] += vis[y];
  }
}

signed main() {
  static char s[Maxn], s1[Maxn];
  int n = read ();
  // clear
  for (int i = 0; i <= tot; ++i)
    fail[i] = v[i] = 0;
  memset (trie, 0, sizeof (trie));
  memset (vis, 0, sizeof (vis));
  tot = 0;
  // read
  for (int i = 1; i <= n; ++i) {
    scanf ("%s", s);
    insert (s, i);
  }
  // build
  build ();
  // query
  scanf ("%s", s1);
  search (s1);
  // count
  for (int i = 1; i <= tot; ++i) {
    add (fail[i], i);
  }
  dfs (0);
  // print
  for (int i = 1; i <= n; ++i) {
    print (vis[id[i]]);
  }
  return 0;
}

后缀自动机 $SAM$

后缀自动机是一个用途广泛的字符串处理算法。 $SAM$ 最重要的，也是它建立的初衷，是它维护了所有子串的信息。具体来说从初始节点 $t_0$ 开始的任意一条路径都与 $s$ 的子串构成对应关系。但这并不能唯一确定一个自动机，因此它还具有一些其他的性质。

令 $endpos(x)$ 为子串 $x$ 在自动机中的所有出现位置。

那么相对于 $endpos(x)$ 只会出现 3 种情况：

$endpos(y) \subseteq endpos(x), \text{当且仅当}\ x \ \text{为}\ y \ \text{的后缀} \\ endpos(y) \supseteq endpos(x), \text{当且仅当}\ y \ \text{为}\ x \ \text{的后缀} \\ endpos(y) \cap endpos(x) = \varnothing, \text{当且仅当}\ x \ \text{和}\ y \ \text{不构成后缀关系}$

（要注意后缀关系与子集关系是反向的）

也有一些子串他们虽然长度不同，但是 $endpos$ 集合是完全相同的，称他们为等价类，这些子串最终会被合并为一个节点。也就是说后缀自动机上每个节点对应的字符串长度是一个区间。

同时维护后缀链接 $fa$ 指向 $endpos$ 真包含当前节点 $endpos$ 集的最长的后缀，即 $longest(fa_x), endpos(fa_x) \supsetneqq endpos(x)$ 。

有了这两个性质辅助，就可以唯一确定一个后缀自动机了。

后缀自动机每个节点维护的基本信息：

$len$ 表示最长等价类长度
$fail$ 表示后缀链接
$sam[\sigma]$ 表示状态转移边
$siz$ 表示每个节点出现的次数

跳 $sam$ 边相当于在后面加字符，跳 $fail$ 边相当于在前面删字符。

后缀自动机的线性构建：

因为 $SAM$ 结构较为复杂，且不确定性因素较多，所以构建分为两步

逐个插入字符，构建 $sam$ 转移边，长度 $len$ 和 $fail$ 指针。
在搭好结构的 $SAM$ 上求 $siz$ 。

设上次插入的点为 $p$ , 这次要插入的点为 $np$ ，令 $len_{np} = len_p + 1$ ，接下来要进行的操作是给 $np$ 找 $fail$ 值。

令 $p$ 重复跳 $fa$ 指针直到找到有相同转移的点或虚拟节点。
如果为虚拟节点， $fail_{np} = 0$ 并退出。
否则令当前节点 $p$ 的对应转移为 $q$ .
可以发现如果当前节点 $len_q = len_p + 1$ ，直接链 $fail$ 并退出。
因为根据上面的定义，这条边不会被后面操作拆开。
否则：
- 新建节点 $nq$ ，并复制 $q$ 除 $len$ 以外的信息。令 $len_{nq} = len_p + 1$ .
  
  相当于强行把 $q$ 删了点东西。
- 将 $fail_q$ 和 $fa_{np}$ 同时指向 $nq$ 。
- 将所有 $fail$ 链接着 $q$ 的点的图边全部替换成 $nq$ 。

这里面最长的串是 $np$ , 最短的串是 $nq$ （如果有的话），从 $np$ 到 $q$ 再到 $nq$ 依次删除了一些前缀。

构建 $siz$ 有两种常见的方法。一种是像 $AC$ 自动机一样反着连 $fail$ 边建出 $fail$ 树，然后跑树形 $dp$ ，另一种是通过特殊性质： $len_{fail_p} < len_p$ ，对映射数组进行时间复杂度为线性的排序来转移。第二种常数较小，且代码相对短。

代码实现：

// 自动机 学习笔记
// 后缀自动机的线性构造
void insert(char c) {
  int p = lst, np = ++tot, ch = c - 'a';
  lst = np, len[np] = len[p] + 1, siz[np] = 1;
  for (; p != -1 && !sam[p][ch]; p = fail[p]) sam[p][ch] = np;
  if (p == -1) return fail[np] = 0, void();
  int q = sam[p][ch];
  if (len[q] == len[p] + 1) return fail[np] = q, void();
  int nq = ++tot;
  fail[nq] = fail[q], fail[q] = fail[np] = nq;
  memcpy(sam[nq], sam[q], sizeof(sam[nq]));
  len[nq] = len[p] + 1;
  for (; p != -1 && sam[p][ch] == q; p = fail[p]) sam[p][ch] = nq;
}

void SAM(char *s) {
  fail[0] = -1, lst = tot = 0;
  int n = strlen(s);
  for (int i = 0; i < n; ++i) insert(s[i]);
  static int cnt[Maxn], id[Maxn];
  for (int i = 0; i <= tot; ++i) ++cnt[len[i]];
  for (int i = 0; i <= tot; ++i) cnt[i] += cnt[i - 1];
  for (int i = 0; i <= tot; ++i) id[--cnt[len[i]]] = i;
  for (int i = tot; i; --i) siz[fail[id[i]]] += siz[id[i]];
}

P3804 【模板】后缀自动机 (SAM)

代码实现：

// 自动机 学习笔记
// Code By CloudySky
#include <bits/stdc++.h>
namespace IO // namespace IO
using namespace IO;
const int Maxn = 2e6 + 10;
using namespace std;

int sam[Maxn][26], siz[Maxn], fail[Maxn], len[Maxn], lst, tot;

void insert(char c) {
  int p = lst, np = ++tot, ch = c - 'a';
  lst = np, len[np] = len[p] + 1, siz[np] = 1;
  for (; p != -1 && !sam[p][ch]; p = fail[p]) sam[p][ch] = np;
  if (p == -1) return fail[np] = 0, void();
  int q = sam[p][ch];
  if (len[q] == len[p] + 1) return fail[np] = q, void();
  int nq = ++tot;
  fail[nq] = fail[q], fail[q] = fail[np] = nq;
  memcpy(sam[nq], sam[q], sizeof(sam[nq]));
  len[nq] = len[p] + 1;
  for (; p != -1 && sam[p][ch] == q; p = fail[p]) sam[p][ch] = nq;
}

char s[Maxn];

void SAM() {
  fail[0] = -1, lst = tot = 0;
  int n = strlen(s);
  for (int i = 0; i < n; ++i) insert(s[i]);
  static int cnt[Maxn], id[Maxn];
  for (int i = 0; i <= tot; ++i) ++cnt[len[i]];
  for (int i = 0; i <= tot; ++i) cnt[i] += cnt[i - 1];
  for (int i = 0; i <= tot; ++i) id[--cnt[len[i]]] = i;
  for (int i = tot; i; --i) siz[fail[id[i]]] += siz[id[i]];
}

signed main() {
  scanf("%s", s), SAM();
  long long ans = 0;
  for (int i = 1; i <= tot; ++i)
    ans = max(ans, siz[i] > 1 ? 1ll * siz[i] * len[i] : 0);
  print(ans);
  return 0;
}

后缀自动机的应用大概要等后续学习了。

回文自动机 $PAM$

回文自动机是一种可以存储一个串中所有回文子串的高效数据结构。同样是一个节点表示一个子串。建出来的形态是两颗树，一颗表示长度为奇数的回文串，

需要维护的东西：

$len$ 字符串长度。
$pam[\sigma]$ 字符边。不同于其他自动机，跳 $pam$ 边的含义是在前面和后面都插入当前字符。
$fail$ 失配边。仍然是指向当前子串的最长后缀。

$PAM$ 的线性构造：

首先构建两个点 $0$ 和 $1$ 分别代表偶根和奇根，并将 $1$ 号点的长度初始化为 $-1$ 。

令 $p$ 为上一次操作后的节点， $q$ 为当前要放入的节点。每插入一个字符不断地令 $p$ 跳 $fail$ 直到可以匹配上回文。显然你的 $q$ 是要接在 $p$ 上的，但是不能着急。先设 $np = fail_p$ ，令 $np$ 不断跳 $fail$ 直到匹配上回文，将 $fail_q$ 指向此时的 $np$ ，然后再将 $pam_p[\sigma]$ 指向 $q$ ，同时 $len_q = len_p + 2$ 。

原因就是 $\exists np = p$ ，如果先 $pam_p[\sigma] = q$ 的话，可能会出现 $fail_q = q$ 的情况，使程序陷入死循环。

代码实现：

// 自动机 学习笔记
// PAM 的线性构造

int pam[Maxn][26], fail[Maxn], len[Maxn], tot，vis[Maxn];

void pam_init () {
  fail[0] = 1, len[1] = -1, tot = 1;
}

void insert (char* s) {
  int n = strlen (s);
  for (int i = 0, x = 0; i < n; ++i) {
    int p = x, q = ++tot;
    while (i - len[p] - 1 < 0 || s[i - len[p] - 1] != s[i])
      p = fail[p];
    if (pam[p][s[i] - 'a'] == 0) {
      int np = fail[p];
      while (i - len[np] - 1 < 0 || s[i - len[np] - 1] != s[i])
        np = fail[np];
      fail[q] = pam[np][s[i] - 'a'];
      // 更新节点信息一定要放到 fail 指针之后，否则可能会把 fail 指向自己
      pam[p][s[i] - 'a'] = q, len[q] = len[p] + 2;
      vis[q] = vis[fail[q]] + 1;
    }
    x = pam[p][s[i] - 'a'];
  }
}

本文作者：CloudySky
写作时间： 2022-01-16
最后更新时间： 2022-01-20
遵循协议： BY-NC-SA

CloudySky || AFO

永远相信美好的事情即将发生。

自动机学习笔记

$AC$ 自动机

后缀自动机 $SAM$

回文自动机 $PAM$

ACACAC 自动机

后缀自动机 SAMSAMSAM

回文自动机 PAMPAMPAM

$AC$ 自动机

后缀自动机 $SAM$

回文自动机 $PAM$