子序列自动机

简介

大概就是用来识别子序列的自动机

在字符集较小的情况下的构建方法如下

for (int i = n; i; --i) {
    for (int j = 0; j < 26; ++j) nxt[i - 1][j] = nxt[i][j];
    nxt[i - 1][s[i] - 'a'] = i;
}

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

当字符集较大的时候，有两个种解决方案，一种是每个字符都扔到 $vector$ 里，另一种是用主席树

两种方法都比较简单，就不放代码了

应用

1. 识别给定序列是否为模板串的子序列

   从根节点跑一边就行

2. 求本质不同的子序列个数

   在自动机上 $dp$ 一下即可

3. 求两个串的公共子序列个数

   将两个串的子序列自动机都建出来，用 $f[i][j]$ 表示到第一个自动机的 $i$ 点和第二个自动机的 $j$ 点方案数，$dp$ 即可

4. 求串的回文子序列个数

   和 $3$ 类似，只要保证 $i+j\le n+1$ 即可

例题

1. 简要题意：给定一个字符串 $s$，求最短的不是 $s$​ 子序列的字典序最小的串

   $|s| \le 2\times 10^5$

   简要题解：我们考虑子序列自动机，我们令 $f[i]$ 表示从 $i$ 跳到 $n+1$ 最小的步数

   转移直接枚举填那个字母，然后根据子序列自动机跳到对应的位置，时间复杂度 $O(26n)$

   AtCoder [ARC081C] Don’’t Be a Subsequence