P3375 【模板】KMP

#include<bits/stdc++.h>
using namespace std;
string s1,s2;
int Next[1000010],len1,len2;
void getNext(string p,int lenp) {
	Next[0] = Next[1] = 0;
	for (int i = 1;i < lenp;i ++) {
		int j = Next[i];
		while (j && p[i] != p[j])
			j = Next[j];
		if (p[i] == p[j]) Next[i + 1] = j + 1;
		else Next[i + 1] = 0;
	}
	return;
}
void kmp(string s,string p,int lens,int lenp) {
	int j = 0;
	getNext(p,lenp);
	for (int i = 0;i < s.size();i ++) {
		while (j && s[i] != p[j])
			j = Next[j];
		if (s[i] == p[j]) ++ j;
		if (j == lenp) {//return i - lenp + 1;
			printf("%d\n",i - lenp + 1 + 1);
			j = Next[j];
		}
	}
	return;
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> s1 >> s2;
	len1 = s1.size();
	len2 = s2.size();
	kmp(s1,s2,len1,len2);
	for (int i = 0;i < s2.size();i ++)
		cout << Next[i + 1] << " ";
	cout << "\n";
	return 0;
}