序列自动机是接受且仅接受一个字符串的子序列的自动机

状态

由子序列的性质，若s包含n个字符，则构造的序列自动机包含\(n+1\)个状态，且每个状态都是终止状态

因此我们可以通过序列自动机获得它的每一个子序列

如abcab的序列自动机如下

我们可以维护一个指针\(to_{i,c}\)，代表s的第i个位置后，第一个字符c所处的位置，若i后没有c了，我们默认指向\(n+1\)

对于例子中的字符串，\(to_{1,b}=2, to_{3,b}=5, to_{4,c}=6\)

这样我们可以通过一个位置x开始不断跳to指针来得到一个s的子序列

为了方便，我们可以设\(to_{0,c}\)是s中第一个c出现的位置，这样跳指针时，设起点\(x=0\)即可

性质

由图可以看出，前n个状态接受长度为\(n-1\)的前缀的所有子序列，则第i个状态接受的是长度为\(i-1\)的前缀有，长度为\(i-2\)的前缀没有的子序列

因此我们可以动态的构造序列自动机，即每在尾部新增一个字符c，就新增一个状态p，让前面所有不能接受c的状态q接受c转移到p

构建

字符集较小

对于字符集较小，如a-z，我们可以直接维护\(to_{i,c}\)

从后往前倒叙枚举每一个位置i，构建\(to_{i,c}\)，维护一个数组las保存c目前出现的最靠前的位置

首先让字符集中搜友字符c都执行\(to_{i,c}:=las_c\)，接着更新\(las_{s_i}=i\)

时间复杂度\(O(N| \text{size}(s)|)\)

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;
	}
}

字符集较大

此时直接维护to指针显然捉襟见肘，我们可以改为使用可持久化线段树维护，即i代表的线段树为它的\(to\)的值

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);
}

应用

判断s是否为t的子序列

将s扔进t的序列自动机，看是否能转移到底
统计s的本质不同子序列个数

记忆化搜索：\(dp[i]=1+\sum_{i\to j} dp[j]\)，加一是因为空序列也是子序列

红魔咖啡馆

【字符串】序列自动机

状态

性质

构建

字符集较小

字符集较大

应用