序列自动机学习笔记

从最长公共子序列开始

首先要先确定子序列的定义，我们认为一个字符串，从中随机地去掉若干个字符，剩下的字符按原顺序排列组成的字符串就是原串的一个子序列。例如，字符串 \(ab\) , \(aa\) , \(bd\) 都是字符串 \(abad\) 的子序列，但是 \(ac\) 不是原字符串的子序列，因为它包含了原串没出现过的字符 \(c\) ； \(db\) 不是原字符串的子序列，因为它虽然包含了原字符串中出现的字符但是它们的顺序不对。

如果一个字符串同时是两个或更多字符串的子序列，那么称这个字符串是它们的公共子序列，公共子序列中长度最长的那些字符串被称为最长公共子序列。

我们知道，求两个字符串的最长公共子序列及其方案数，可以用动态规划DP来求出。但如果我们需要求三个字符串的最长公共子序列长度，或者更多数量字符串的最长公共子序列长度呢？有没有一种方法，可以快速判断某个串是不是字符串的子序列呢？

事实上，有一种有限状态自动机，它是接受且仅接受一个字符串子序列的自动机，它就是序列自动机。

序列自动机的实现

序列自动机的构造

虽然序列自动机也是有限状态自动机的一种，但是与AC自动机、后缀自动机相比，它的原理相当地简单。作为一种自动机，它接受且仅接受一个字符串的子序列。先来看一下它的构造代码。注意这里的字符串 \(s\) 的下标从 \(1\) 开始。

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

其中 \(nxt[i][j]\) 表示第 \(i\) 个位置之后（不包含第 \(i\) 个位置） 字符 \(j\) 第一次出现的位置，如果没有则为 \(0\) 。这段代码也十分简单，将第 \(i\) 位置的 \(nxt\) 数组赋给 \(i-1\) 位置，然后单独修改 \(s[i]\) 对应的数组。构造出来的 \(nxt\) 数组应该是长这样的。

然后就…没了。

有人可能会说，哎有限状态自动机不应该看起来像一个DAG吗，怎么变成一个数组了？实际上，刚才的 \(nxt\) 数组就已经描述了序列自动机所有的出边关系。那么将上面的 \(nxt\) 数组描绘出来，就变成了下面的DAG。其中 \(nxt[i][j]\) 表示节点 \(i\) 有一条代表字符 \(j\) 的出边指向 \(nxt[i][j]\) 结点。

序列自动机的应用

1.判断是否是原串的子序列

这个应用是序列自动机最基础的应用，通常会结合其他算法使用来判断某个串是不是另一个串的子序列。比如 P4112 [HEOI2015] 最短不公共子串 ，就会同时使用序列自动机和后缀自动机判别子序列和子串。

2.求一个字符串的子序列的数量

有人可能想说，哎根据排列组合，这不就是 \(2^n\) 吗？某种意义上这是对的，但这里我们讨论的子序列的数量是去重后的数量。我们知道自动机不会接受重复的子序列，因此我们可以在序列自动机的DAG上跑DP即可。另外，用容斥原理也可以解决求字符串子序列的问题。这里给出两种做法的参考代码。

struct sequence_automate
{
	int ch[MAXN][26],len;
	sequence_automate()
	{
		memset(ch, 0, sizeof(ch));
		len = 0;
	}
	void build(char* s)
	{
		len = strlen(s);
		memset(ch, 0, sizeof(ch));
		memset(pre, 0, sizeof(pre));
		for (int i = len; i >= 1; i--)
		{
			for (int j = 0; j < 26; j++)
			{
				ch[i - 1][j] = ch[i][j];
			}
			if (ch[i - 1][s[i - 1] - 'a'])
			{
				pre[ch[i - 1][s[i - 1] - 'a']] = i;
			}
			ch[i - 1][s[i - 1] - 'a'] = i;
			for (int j = 0; j < 26; j++)
			{
				if (ch[i - 1][j]) edge_in[ch[i - 1][j]]++;
			}
		}
	}
	void solve1()
	{
		long long ans = 0;
		memset(f1, 0, sizeof(f1));
		f1[0][0] = 1;
		queue<int> q;
		q.push(0);
		while (!q.empty())
		{
			int now = q.front();
			q.pop();
			for (int i = 0; i < 26; i++)
			{
				if (!ch[now][i]) continue;
				edge_in[ch[now][i]]--;
				if (!edge_in[ch[now][i]]) q.push(ch[now][i]);
				for (int j = 0; j <= now; j++)
				{
					f1[ch[now][i]][j + 1] += f1[now][j];
					ans+= f1[now][j];
				}
			}
		}
		printf("%lld\n", ans);
	}
	void solve2()
	{
		f2[0] = 1;
		for (int i = 1; i <= len; i++)
		{
			f2[i] = f2[i - 1] * 2;
			if (pre[i]) f2[i] -= f2[pre[i] - 1];
		}
		printf("%lld\n", f2[len] - 1);
	}
}seq_a;

3.求若干个字符串的不同的公共子序列数量

运用搜索，贪心地寻找当前位置后相同字母的位置。因为匹配时寻找到的位置越靠前，在字符串的后面部分就越有可能匹配到新的公共子序列，还不会导致计算重复。

这里以 P1819 公共子序列 为例。

long long dfs(int x,int y,int z)
{
	if (f[x][y][z]) return f[x][y][z];
	for (int i = 0; i < 26; i++)
	{
		if (nxt[0][x][i] && nxt[1][y][i] && nxt[2][z][i])//贪心地寻找当前位置后相同字母的位置
		{
			f[x][y][z] = (f[x][y][z] + dfs(nxt[0][x][i], nxt[1][y][i], nxt[2][z][i])) % mod;
		}
	}
	if (x && y && z) f[x][y][z] = (f[x][y][z] + 1) % mod;
	return f[x][y][z];
}