基因改造 题解

前言

题目链接：Hydro & bzoj。

题意简述

求匹配串 \(S\) 中和模式串 \(T\) 匹配的子串。两个串被定义为匹配的，当且仅当一个串任意交换字符后和另一个串相等。例如 \(\texttt{12321}\) 和 \(\texttt{21312}\) 匹配，因为前者交换 \(\texttt{1}\) 和 \(\texttt{2}\) 后与后者等价。当然，可以和一个串中不出现的字符交换。

题目分析

如果直接求匹配很板子，但是题目重新定义了匹配，所以考虑把这个匹配转换成我们熟悉的形式。

敏锐地发现，两个串匹配，当且仅当存在一个映射，把一个串通过这个映射变换后和另一个串相等。

进一步发现，和每一种字符的相对位置有关。考虑对于一个串的每一个位置，处理出该位置和上一次出现这个值的位置之差，作为该位置新的关键值用于比较。特殊地，如果从来没有出现，记上一次出现的位置为 \(0\)。

对于匹配串和模式串，我们都可以预处理出这样一个数组，匹配的时候拿这两个数组匹配即可。当然，如果在匹配串中某一个位置，其关键值大于了当前匹配到的长度，则当做没有出现过处理即可。

这么做的正确性是显然的。

代码

void solve() {
	read(n), read(m), memset(idx, 0x00, sizeof (int) * (V + 1));
	for (int i = 1, x; i <= n; ++i) read(x), S[i] = i - idx[x], idx[x] = i;
	memset(idx, 0x00, sizeof (int) * (V + 1));
	for (int i = 1, x; i <= m; ++i) read(x), T[i] = i - idx[x], idx[x] = i;
	tot = 0, T[m + 1] = S[n + 1] = 0;
	for (int i = 1, j = fail[0] = -1; i <= m; ++i) {
		while (~j && !(T[i] == T[j + 1] || (T[i] > j && T[j + 1] > j))) j = fail[j];
		fail[i] = ++j;
	}
	for (int i = 1, j = 0; i <= n; ++i) {
		while (~j && !(S[i] == T[j + 1] || (S[i] > j && T[j + 1] > j))) j = fail[j];
		++j;
		if (j == m) ans[++tot] = i - j + 1;
	}
	write(tot), putchar('\n');
	for (int i = 1; i <= tot; ++i) write(ans[i]), putchar(' ');
	putchar('\n');
}