#1#2#3#12#13#14 AC 其他 TLE

代码：

#include <iostream>

using namespace std;

const int N = 1e7 + 5;

int ret[N];
int lena, lenb;

void get_ret(string &b) {
	int las_presuf = 0, i = 1;
	//las_presuf : (上次)当前最长前后缀长度
	while (i < lenb) {
		if (b[las_presuf] == b[i]) //可以续
			las_presuf ++, ret[i ++] = las_presuf;
		else { //不可以续之前的, 重造可以续的
			if (las_presuf)
				las_presuf = b[las_presuf - 1];
			else //重新来
				ret[i ++] = 0;
		}
	}
}

void kmp(string &a, string &b) {
	get_ret(b);

	int i = 0, j = 0;
	while (i < a.size()) {
		if (a[i] == b[j]) //当前可以匹配
			i ++, j ++;
		else //不能匹配
			if (j)
				j = ret[j - 1];
			else
				i ++;

		if (j == lenb) //成功
			printf ("%d\n", i - j + 1);
	}
}

int main() {
//	freopen ("kmp.in", "r", stdin);
//	freopen ("kmp.out", "w", stdout);

	string a, b;
	cin >> a >> b;
	lena = a.size(), lenb = b.size();

	kmp(a, b);

	for (int i = 0; i < lenb; i ++)
		printf ("%d ", ret[i]);
	return 0;
}