RT

本蒟蒻想用kmp写这个题。

这里删除用的是双向链表（仅a数组，没有用）。

匹配成功就删除前m个。

删除后向前跳m+1个以防遗漏。

交上去wa on 4，too short on line 1。

（竟然没有TLE）

#include <stdio.h>
#include <string.h>
#define N 10000006
int lv[N], rv[N], next[N];
char a[N];
int n, m;
char b[N];

void getnext() {
	int i = 2, j = 0;
	while (i <= m) {
		while (j && b[i] != b[j + 1])
			j = next[j];
		if (b[i] == b[j + 1])
			j++;
		next[i] = j;
		i++;
	}
}

void kmp() {
	int i = 1, j = 0, k = 0, tm = m;
	while (i <= n) {
		while (j && a[i] != b[j + 1])
			j = next[j];
		if (a[i] == b[j + 1])
			j++;
		i = rv[i];
		if (j >= m) {
			tm = m;
			k = lv[i];
			while (tm--)
				k = lv[k];//第一次向前跳
			rv[k] = i;//删除操作
			lv[i] = k;
			j = 0;//向前跳了m+1个，应该可以直接让j=0
			i = k;
			tm = m;
			while (i && tm--)
				i = lv[i];//第二次向前跳
			if (!i)//判0
				i = rv[i];
			else if (!lv[i])
				i = lv[i];
		}
	}
}

int main() {
	register int i, j;
	scanf("%s", a + 1);
	n = strlen(a + 1);
	scanf("%s", b + 1);
	m = strlen(b + 1);
	for (i = 1; i <= n; ++i) {
		lv[i] = i - 1;
		rv[i] = i + 1;
	}//初始化
	getnext();
	rv[0] = 1;
	kmp();
	for (i = rv[0]; i <= n; i = rv[i]) {
		putchar(a[i]);
	}
	return 0;
}

dalao帮忙看一下吧，qql