洛谷上KMP题目的模板

#include<bits/stdc++.h>
using namespace std;
void getNext(vector<int>& next, string str) {
	next[0] = 0;
	int i, j = 0;
	for (i = 1; i < next.size(); i++) {
		while (j > 0 && str[j] != str[i]) {
			j = next[j - 1];
		}
		if (str[j] == str[i]) {
			j++;
		}
		next[i] = j;
	}
}
void KMP(vector<int>& next, string str1, string str2) {
	//模式串求next数组
	int i, j;
	for (i = 0; i < str2.size(); i++) {
		next.push_back(0);
	}
	i = 0, j = 0;
	getNext(next, str2);
	while (i < str1.size()) {
		if (str1[i] == str2[j]) {
			j++; i++;
		}
		else {
			if (j == 0) i++;
			else j = next[j - 1];
		}
		if (j == str2.size()) {
			cout << i - j + 1 << endl;
			j = next[j - 1];
		}
	}

}
int main() {
	string str1, str2;
	cin >> str1 >> str2;
	vector<int> res; vector<int> next;
	KMP(next, str1, str2);
	for (auto item : next) {
		cout << item<<' ';
	}
	return 0;
}