题解

序列自动机即一种建立在序列上的有穷自动机。有字符集，状态集合，起始状态，接收状态集合，转移函数五个要素。

其基本操作包括以下三种：

  1. 统计一个串本质不同的子序列的个数。(复杂度为$O(n*|S|)$)

  2. 查找一个子序列是否在该串中出现过。(复杂度为$O(n*|S|)$)

  3. 找到两个串所有的公共子序列。(复杂度为$O(nn|S|)$)

这三种操作的状态集合即位置集合$0~n$，起始状态即位置$0$，接收状态集合为所有状态，转移函数和第一种操作的具体实现如下。

代码

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

int dfs(int x){
	if(vis[x])return f[x];
	f[x]=1;
	for(int i=0;i<26;++i)
	if(nex[x+1][i]){
		f[x]+=dfs(nex[x+1][i]);
	}
	vis[x]=true;
	return f[x];
}