kmp算法（相当于实现C/C++标准库中的strstr函数）

buhuizhiyuci

903人浏览 · 2025-11-14 17:27:13

buhuizhiyuci · 2025-11-14 17:27:13 发布

最近学习了一些kmp算法有些感受

这里只是对kmp算法的粗略介绍其实大家自己动手画图会有更深刻的理解希望大家结合图像去看

文章可能会讲述的不清楚————结合图像去理解，代码部分可以用一些简单的值去推一下其看看代码的走向是什么样子的能够帮助你们更加深刻的去理解代码

画图画图画图！！！

首先介绍kmp算法我们需要知道一些知识

kmp算法一般是判断字符串所以我们可以先定义一个字符串

#include<iostream>
#include <string>
using namespace std;
int main()
{
	string a = "hello word";
	size_t sa = a.size();
	a = ' ' + a;
	return 0;
}

这里看到我们定义了一个字符串，字符串的下一行是计算它的大小，在下一步加空格的目的是让这个字符串在‘1’这个位置进行计数，这样方便后续的计数，计算大小和它的下一行尽量不要交换，因为他是计算不加空格这个地方的值如过调换了后续在循环的时候要将”=“给去掉。

这里我们先了解一下它所需要的一些基础知识（后续的值都以”abaaba来举例“）

子串：就是连续的字符个数。这里是 a ab aba abaa abaab abaaba baa.......。

前缀：就是从首元素开始连续的字符。这里是a ab aba abaa abaab abaaba。

真前缀：简单来说就是前缀去掉那个存有整个字符串的数。这里是a ab aba abaa abaab。

后缀：与前缀相反包括后面首元素的连续字符。这里是a ba aba aaba baaba abaaba。

真后缀：简而言之与真前缀相同的是都不包括那个存在真个数组的结果。这里是a ba aba aaba baaba。

真公共前后缀--border：公共前后缀就是前缀和后缀相同的一类数据，已这个例子为例

Π（1）——a——》0无真公共前后缀

Π（2）——ab——》0同上

Π（3）——aba——》1真公共前后缀为前缀的序号为1的a和后缀的序号为3的a

......

Π（6）——abaaba——》3真公共前后缀为前缀aba和后缀的aba

注意这里的Π值是真公共前后缀的最大值。

前缀函数

是采用动态规划的思想来遍历真个数组的方法，这里主要用到的思想为就是列举出所有数据来进行推到推出最后一个数据。

前缀函数解析
0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0

1 2 3 4 5 6 7 8 9 ...... i-1 i
在这里展示的一个0就是一个数据

假设这个前i-1的Π值为2就是前缀的1 和 2与后缀为i-2和i-1的数相等接下来我们就要判断假设第二行设置一个指针j指向二的位置随后我们根据动态规划的思想来实验如果j+1的位置和i这个位置相等那他无疑就是做大的border

那如果不相等那就是不是【1，i】之间的border那我们就返回去寻找前一个最大的border怎办寻找呢真理观察发现j这个位置是一个border那我们给他之间挑一个Π来寻找下一个（即Π（j））如果不行那就继续找继续取Π

知道条件一：找到j+1和i相等的位置。条件二：j=0的时候（取值的时候j值是一直发生改变的）j=0的时候我们在初始化的时候就已经放了空格所以他的值为0进不去循环的

这里来一到习题呈现给大家

代码呈现、

#include<iostream>

using namespace std;

const int N = 2e6 + 10;
string s1, s2;//s1字串  s2是模式串
int pi[N];//相当于一个排统计个数所用
int n, m;
int main()
{
	cin >> s1 >> s2;
	n = s1.size(); m = s2.size();
	s1 = ' ' + s2 + '#' + s1;
	for(int i=2;i<=m+n+1;i++)
	{
		int j = pi[i - 1];
		while (j && s1[j + 1] != s1[i])j = pi[j];
		if (s1[j + 1] == s1[i])j++;
		pi[i] = j;
		if (pi[i] == m)
		{
			cout << i - 2 * m <<endl;
		}
	}
	for (int i = 1; i <= m; i++)cout << pi[i] << " ";
	return 0;
}

收先pi就是上述所说的Π这里的pi内部的值首先全部为零

进入for循环的第一行就是动态规划的思想将最后一位的前一位给 j因为他如果是真公共前后缀的话那他的j位和i-1位必须相等（去用j+1与i看看是否相等），进入while循环的条件是j！=0，判断的那两个位置数据不相等如果进入那就往前跳找他前一个适合的如果是和就会跳出不适合除非跳到j=0这个位置，如果进入if表示他两箱等那就让j的++去找笑一个知道找到与m相等的数

（s1）的那个位置就是将那两个字符串拼接去找后续的内容“#”这里可以不是这个值只要字符串中没有就能加进去使用

i-2*m他的是指这个最大真公共前后缀的首元素这个是公式直接记住即可