子序列自动机是什么？
下文的 S 默认指一个长度为 n 的字符串 S，S_i 代表 S 的第 i 位，c 代表一个字符。
简介
长度为 n 的字符串 S，它的子序列指从 S 中将若干元素提取出来并不改变相对位置形成的序列，即 S_{p_1},S_{p_2},...,S_{p_k}，其中 1\le p_1<p_2<\cdot\cdot\cdot<p_k\le n。
子序列自动机（Subsequence automaton，翻译自百度翻译）， 是接受且仅接受一个字符串的子序列的自动机，是一个处理子序列的锐利武器。
对于一个字符串 S，我们可以通过使用子序列自动机得到它的每一个子序列，并方便地去维护、查询它们，让人惊喜不已。
状态
oi-wiki 上有形式化的说明，这里给出一个更易理解的版本：
我们维护指针 to_{i,c}，其中 i 是一个数字、c 是一个字符。它代表 S 的第 i 个位置后，第一个字符 c 所处的位置。如果 i 位置后没有 c 了，我们可以默认它指向 n+1。
比如 S="abcdc"，那么 to_{1,'d'}=4,to_{2,'c'}=3,to_{3,a}=6。
这样，我们可以通过从一个位置 x 开始不断跳 to 指针来得到一个 S 的子序列。
因此，为了方便，我们可以设 to_{0,c} 为 S 中第一个 c 所出现的位置，这样跳指针时，设起点 x=0 即可。
为什么 to_{i,c} 是指向 i 后面第一个字符 c 所处的位置，而不是第二个、第三个？
对于两个位置 j,k 且 j 在 k 的前面，如果它们位置上的字符是一样的，都是 c，那么以 k 开头的子序列的集合，肯定是以 j 开头的子序列的集合 的子集。所以我们可以采取贪心的思想，贪得无厌地选第一个位置，真是大快人心！
子序列自动机怎么构建？
字符集较小
对于字符集较小的情况（比如字符集为 a~z），我们可以直接去维护 to_{i,c}。
倒行逆施地，我们从后往前，倒序枚举每一个位置 i，构建 to_{i,c}。
巧夺天工地维护一个数组 las， las_c 代表 c 目前出现最前的位置。
首先我们让字符集里的所有字符 c，都执行操作 to_{i,c}:=las_c。接着更新 las，令 \large las_{S_i}=i 即可。
时间复杂度为 O(n|\sum|)，|\sum| 为字符集大小。
void build(){
for(int i=1;i<=m;++i)las[i]=n+1;
for(int i=n;i>=1;--i){
for(int j=1;j<=m;++j)to[i][j]=las[j];
las[ S[i] ]=i;
}
}
字符集较大
如果不随人愿，字符集较大（比如字符集大小为 10^5），那么直接维护 to_{i,c}，时间和空间复杂度都是庞然大物。改为用可持久化线段树去维护，也就是 i 代表的线段树为它的 to 的值。
因为 i 的改变，只会让 las 改变一个位置的值，这就相当于单点修改，所以时间复杂度是 O(n\log |\sum|) 的。
void plant0(int &o,int l,int r){
dcnt++,o=dcnt;
if(l==r){tre[o].val=n+1;return;}
int mid=(l+r)>>1;
plant0(tre[o].lv,l,mid),plant0(tre[o].rv,mid+1,r);
}
void plant(int ori,int &o,int l,int r,int wei,int val){
dcnt++,o=dcnt;
tre[o]=tre[ori];
if(l==r){tre[o].val=val;return;}
int mid=(l+r)>>1;
if(wei<=mid)plant(tre[ori].lv,tre[o].lv,l,mid,wei,val);
if(wei>mid) plant(tre[ori].rv,tre[o].rv,mid+1,r,wei,val);
}
int query(int o,int l,int r,int wei){
if(l==r)return tre[o].val;
int mid=(l+r)>>1;
if(wei<=mid)return query(tre[o].lv,l,mid,wei);
if(wei>mid) return query(tre[o].rv,mid+1,r,wei);
}
void build(){
plant0(rot[n],1,m);
for(int i=n;i>=1;--i)plant(rot[i],rot[i-1],1,m,S[i],i);
}
UPD：可以用一种更简洁的方法构建自动机。我们给每一个字符开一个 vector，存储着这个字符出现的所有下标。每次查询 to_{i,c}，就是在 c 对应的 vector 里面二分出第一个大于等于 i 的下标。
子序列自动机有什么用？
例题：P5826 - 【模板】子序列自动机
https://www.luogu.com.cn/problem/P5826
题意
给定字符串 S，T 次询问，每次询问一个字符串 B 是否为 S 的子序列。
#### 题解
注意：第一篇 WYXkk 的题解不是本文所说的子序列自动机，一扶苏一 的题解才是。
我们需要查询一个字符串 $B$ 是否为 $S$ 的子序列。根据对子序列自动机的理解，我们可以将内忧外患迎刃而解。
让 $B$ 和 $S$ 匹配，也就是在自动机上跑，用指针 $k$ 指向 $S$ 匹配到了哪里。
假如正在试图匹配 $B_i$，那么我们让 $\large k=to_{k,B_i}$。如果 $k=n+1$ 说明匹配失败，$B$ 不是 $k$ 的子序列。如果匹配完 $B$ 了，仍有 $k\le n$ 那么代表 $B$ 是 $k$ 的子序列。
#### 代码
完整[代码](https://www.luogu.com.cn/record/64584795)，干净又卫生，让人大快朵颐：
```c++
#include<bits/stdc++.h>
#define rep(i,x,y) for(int i=x;i<=y;++i)
#define per(i,x,y) for(int i=x;i>=y;--i)
#define lon long long
using namespace std;
const int n7=101234,m7=102,t7=n7*32;
struct dino{int val,lv,rv;}tre[t7];
int n,T,m,L,dcnt,S[n7],b[n7],to[n7][m7],las[n7],rot[n7];
int rd(){
int shu=0;bool fu=0;char ch=getchar();
while( !isdigit(ch) ){if(ch=='-')fu=1;ch=getchar();}
while( isdigit(ch) )shu=(shu<<1)+(shu<<3)+ch-'0',ch=getchar();
return fu?-shu:shu;
}
void plant0(int &o,int l,int r){
dcnt++,o=dcnt;
if(l==r){tre[o].val=n+1;return;}
int mid=(l+r)>>1;
plant0(tre[o].lv,l,mid),plant0(tre[o].rv,mid+1,r);
}
void plant(int ori,int &o,int l,int r,int wei,int val){
dcnt++,o=dcnt;
tre[o]=tre[ori];
if(l==r){tre[o].val=val;return;}
int mid=(l+r)>>1;
if(wei<=mid)plant(tre[ori].lv,tre[o].lv,l,mid,wei,val);
if(wei>mid) plant(tre[ori].rv,tre[o].rv,mid+1,r,wei,val);
}
int query(int o,int l,int r,int wei){
if(l==r)return tre[o].val;
int mid=(l+r)>>1;
if(wei<=mid)return query(tre[o].lv,l,mid,wei);
if(wei>mid) return query(tre[o].rv,mid+1,r,wei);
}
void build(){
plant0(rot[n],1,m);
per(i,n,1)plant(rot[i],rot[i-1],1,m,S[i],i);
}
bool check(){
int now=0;
rep(i,1,L){
now=query(rot[now],1,m,b[i]);
if(now==n+1)return 0;
}
return 1;
}
int main(){
rd(),n=rd(),T=rd(),m=rd();
rep(i,1,n)S[i]=rd();
build();
while(T--){
L=rd();
rep(i,1,L)b[i]=rd();
if(L>n)puts("No");
else puts(check()?"Yes":"No");
}
return 0;
}
```
### P4608 - [FJOI2016]所有公共子序列问题
<https://www.luogu.com.cn/problem/P4608>（三倍经验 [这](https://www.luogu.com.cn/problem/P1819)，[那](https://www.luogu.com.cn/problem/P3856)）
#### 题意
求两个字符串 $S,T$ 的公共子序列个数。
字符串长度小于等于 $3010$。
#### 题解
可以把子序列自动机看做一个图，连边 $i\to to_{i,c}$，那么从 $0$ 号点出发，任意一条路径就是一个子序列。
对于 $S,T$ 都构建自动机，分别称为 $to,to'$。
对于 `k=0` 我们可以搜索，枚举当前子序列可以接上的字符 `c`，搜索即可。
对于 `k=1`，触类旁通地，我们想到用 dp 解决问题。
设 $f_{i,j}$ 为从 $S_i$ 与 $T_j$ 开始的公共子序列的个数。
既然如此，有：
$$
\Large f_{i,j}=\sum\limits_{c\in \text {alphabet}} f_{to_{i,c},to'_{j,c}}
$$
可以用记忆化搜索实现，鬼斧神工！
### P4112 - [HEOI2015]最短不公共子串
<https://www.luogu.com.cn/problem/P4112>
这里只做第 2、4 问，因为其余问的解法是 SAM，而非子序列自动机算法。
#### 题意
给定两个字符串 $S,T$，分别长为 $n,m$，求：
- $S$ 的一个最短的子串，它不是 $T$ 的子序列，输出其长度。
- $S$ 的一个最短的子序列，它不是 $T$ 的子序列，输出其长度。
字符串长度小于等于 $2000$。
#### 题解
给 $T$ 修筑一个子序列自动机。
第一问：
枚举 $S$ 的子串，用 $T$ 的子序列自动机判断其是否为 $T$ 的子序列即可。
第二问：
触类旁通地，我们使用 dp。
设 $f_{i,j}$ 为从 $S_i$ 开始的一个子序列 $B$，长度最小为多少，才能让 $B$ 不是从 $T_j$ 开始的某个子序列。
则有：
$$
\Large f_{i,m+1}=0\\\Large f_{i,j}=\min\limits_{c\in \text{alphabet}} \{f_{to_{i,c},to_{j,c}}+1\}
$$
意思就是说，$f_{i,j}$ 可以通过在 $B$ 后面拼接一个字符 $c$，那么就是对应的状态加上 1 的长度。
倒序转移 dp 即可，答案显然为 $f_{0,0}$。
## 参考文献
<http://oi-wiki.com/string/seq-automaton>
<https://www.luogu.com.cn/blog/fusu2333/solution-p5826>
再次感谢您的支持！