RT

我写的是下标 0 开始的，根据自己的理解，可能写的比较奇怪

发现如果模式串的最后一项如果是 -1，模式串和文本串进入了部分匹配的话就会 RE

#include <bits/stdc++.h>

using namespace std;

const int Maxn = 1e6 + 5;

int prefix[Maxn];

string text, pattern;

int ans;

inline void Init() {
	prefix[0] = -1;
	for(register int i = 1; i < pattern.size(); ++i) {
		int j = prefix[i - 1];
		while(pattern[j + 1] != pattern[i] && j != -1) j = prefix[j];
		prefix[i] = (pattern[j + 1] == pattern[i] ? j + 1 : -1); 
	}
}

int main() {
	cin >> text >> pattern;
	Init();
	int j = 0;
	for(register int i = 0; i < text.size(); ++i) {
		while((text[i] != pattern[j]) && (j > 0)) j = prefix[j - 1] + 1;
		if(j == pattern.size() - 1) {printf("%d\n", i - pattern.size() + 2); j = prefix[j] + 1;}
		else j++;
	}
	for(register int i = 0; i < pattern.size(); ++i) printf("%d ", prefix[i] + 1);
	return 0;
}