[数据结构与算法]KMP(吉林大学数据结构)C++

这里只记录代码，不对算法本身再次讲解（此代码下标从0开始）

#include <iostream>

using namespace std;

const int N = 100010;
char s[N], p[N];
int ne[N];//所谓失误函数

int main()
{
	cin >>s>> p;
	ne[0] = -1;
	int m = strlen(p);
	//next数组构建（失误函数）
	for (int i = 1, j = -1; p[i]; i++)
	{
		while (j >=0 && p[i] != p[j + 1])j = ne[j];
		if (p[i] == p[j + 1])j++;
		ne[i] = j;
	}
	for (int i = 0; p[i]; i++)printf("%d ", ne[i]);
	//匹配过程
	puts("");
	for (int i = 0, j = -1; s[i]; i++)
	{
		while (j >=0 && s[i] != p[j + 1])j = ne[j];
		if (s[i] == p[j + 1])j++;
		if (j + 1 == m)printf("%d ", i - m+1);
	}
	return 0;
}