Bzoj3942 Censoring(KMP)

$KMP$问题的核心在于数组$next$(或者$pre$/$fail$，各种叫法)，几乎所有的此类型题都是需要计算$next$的。

这里解释一波$next$:即满足字符子串$s[1...k]=s[j-k+1...j]$的最大$k$。比如说：

字符串$abaca$的$next[5]$就是$1$，因为只有$s[1]=s[5]$。

而字符串$abcab$的$next[5]$就是2，同理，$s[1...2]=s[4...5]$。

弄清楚了这一点，来看题目，显然，这道题的难点在于删除字符后有可能对前面已经匹配完了的字符产生新一次的匹配，因为后面新加入的字符可能对前面的字符有贡献。

既然这样，我们不妨设一下四个变量:$i,j,k,l$（所有字符串从$0$开始）。

其中$i,l$表示当前需要将$S_i$加入到$U_l$中，$j$表示当前匹配到了$T_j$，$k$表示当前已经匹配到$U_k$。

如果当$k==l$时，代表前$k-1$个字符已经匹配完，添加新字符。
接下来就是调整$next$和判断是否匹配，同普通$KMP$算法。
！！重点：当$j==lenT$即已经匹配完了，则将$j$归零，将$l$减去$lenT$示删去了$lenT$个字符，因为$l$就是新串的长度，接下来，我们直接将$k$减去$lenT\times 2$因为前面最多会有$lenT-1$个字符与$T$匹配，特判一下当$k<0$时将$k$置为$0$就可以了。

#include <cstdio>

#include <cstring>

const int Len = 1e6 + 10;

char S[Len], T[Len], U[Len];

int lenS, lenT, nxt[Len];

void init () {

	for (int i = 1, j = 0; i < lenT; ++i) {

		while (j && T[i] != T[j]) j = nxt[j];

		j += (T[i] == T[j]), nxt[i + 1] = j;

	}

} 

int main () {

	scanf ("%s%s", S, T);

	lenS = strlen (S), lenT = strlen(T);

	init ();

	int l = 0, k = 0, i = 0, j = 0;

	while (i < lenS) {

		if (k == l)	U[l++] = S[i++];

		while (j && U[k] != T[j]) j = nxt[j];

		j += (U[k] == T[j]);

		if (j == lenT) {

			j = 0, l -= lenT;

			k -= lenT << 1;

		}

		if (k < 0) k = 0;

		else ++k;

	}

	for (int i = 0; i < l; ++i)

		putchar (U[i]);

	return 0;

}

巴特西

Bzoj3942 Censoring(KMP)

最新文章

热门文章