题解 P5826 【【模板】子序列自动机】
y2823774827y
2019-12-18 19:24:44
[更好的阅读体验](https://www.cnblogs.com/y2823774827y/p/10619179.html)
## 序列自动机
- **构造**
$a$是字符集，$|s|=n$，$nxt[i][j]$表示$i$以后的第一个字符$j$的位置，$0$为根节点，整个图是一个$DAG$
```cpp
for(LL i=n;i>=1;--i){
for(LL j=1;j<=a;++j) nxt[i-1][j]=nxt[i][j];
nxt[i-1][s[i]]=i;
}
```
- **扩展构建**
当字符集较大时，可套用可持久化，在叶子节点放一个$id$，表示出边。
相关例题：
字符串$K$小子序列，可持久化序列自动机，维护节点大小。
一步一步(从首到尾)走，有序确定[code](https://www.luogu.org/paste/t9xrb852)
## 经典例题
- **判断是否是原字符串的子序列**
构造出了$nxt$后，从根跑一遍就好了。
- **求子序列个数**
从根跑，记忆化搜索，$f[x]$为点$x$为首的子序列个数，$f[y]=(\sum\limits_{x\in y'son}f[x])+1$
- **求两串的公共子序列个数**
两串都构造一下，之间跑就好了。
```cpp
LL Dfs(LL x,LL y){
if(f[x][y]) return f[x][y];
for(LL i=1;i<=a;++i)
if(nxt1[x][i]&&nxt2[y][i])
f[x][y]+=Dfs(nxt1[x][i],nxt2[y][i]);
return ++f[x][y];
}
```
- **求字符串的回文子序列个数**
原串与反串都建一遍
$$\begin{aligned}\longrightarrow
1~~2~~3~~4~~5~~6~~7~~8~~9~~10&\\
10~~9~~8~~7~~6~~5~~4~~3~~2~~1&\longleftarrow\\
\end{aligned}$$
就相当于从左右端点这样跑。
求的时候显然$x+y≤n+1$这个序列才是合法的。
$x+y=n+1$时就是会合了一样，在之后的遍历过程会$++f[x][y]$，所以暂时不统计。
但是其他情况我们都是匹配的两个字符，也就是只会统计$abba$，而统计不了$aba$，所以在过程中$++f[x][y]$
```cpp
LL Dfs(LL x,LL y){
if(f[x][y]) return f[x][y];
for(LL i=1;i<=a;++i)
if(nxt1[x][i]&&nxt2[y][i]){
if(nxt1[x][i]+nxt2[y][i]>n+1) continue;
if(nxt1[x][i]+nxt2[y][i]<n+1) f[x][y]++;
f[x][y]=(f[x][y]+Dfs(nxt1[x][i],nxt2[y][i]))%mod;
}
return ++f[x][y];
}
```
- **求一个$A,B$的最长公共子序列$S$，使得$C$是$S$的子序列**
还是同样的$Dfs(x,y,z)$，表示一匹配到$C$的$z$位。
改变一下$C$的构建方法
```cpp
for(LL i=1;i<=a;++i) nxt[n][i]=n;
for(LL i=0;i<n;++i){
for(LL j=1;j<=a;++j) nxt[i][j]=i;
nxt[i][c[i+1]]=i+1;
}
```