KMP题解代码（含讲解）

const int N = 1e6 + 5;

int nextt[N];

void GetNext(const string& p)
{
	nextt[1] = 0;
	int n = p.size() - 1;//因为在字符串前面加了个'0'，所以字符串的长度 = 字符串的size - 1
	for (int i = 2, j = 0/**/; i <= n; i++)
	{
		while (j && p[j + 1] != p[i])
			/*注意有一个 + 1，要判断的是下一个位置是否和i位置相等*/
			j = nextt[j];//回退

		if (p[j + 1] == p[i])//如果匹配上了
			j++;//继续往后走，不回退
		nextt[i] = j;//注意是next[i]，并不是next[j]
	}
}

void KMP(const string& s, const string& p)
{
	int len1 = s.size() - 1;
	int len2 = p.size() - 1;//因为在字符串前面加了个'0'，所以字符串的长度 = 字符串的size - 1

	for (int i = 1/**/, j = 0; i <= len1/*注意是遍历母串*/; i++)
	{
		while (j && p[j + 1] != s[i]/*子串的j + 1和母串的i不匹配*/)
			j = nextt[j];//回退

		if (p[j + 1] == s[i])//如果匹配上了
			j++;//继续往后走，不回退

		//题目要求的输出
		if (j == len2)
			cout << i - len2 + 1 << endl;
	}
}

void solve()
{
	string s, p;//母串，子串（模式串）
	cin >> s >> p;
	s = '0' + s;//注意下标从1开始
	p = '0' + p;

	GetNext(p);
	KMP(s, p);

	int len1 = s.size();
	int len2 = p.size();
	for (int i = 1/*从1开始*/; i < len2; i++)
		cout << nextt[i] << " ";
	cout << endl;
}

int main()
{
	solve();
	return 0;
}