直观清晰的带你了解KMP算法(超详细)

本文介绍: 如果我们要找p[10]的下标呢？同上，先看p[9]的下标为3，对吧，我们看p[9]和p[3]，发现根本不相等，怎么办呢？那么我们就从p[3]对应的next值入手，p[3]对应的next 值为0，我们再回退到0，发现第p[0]与p[10]相等，这里 p[0]的next的值就是对应的p[10]next值+1啦！我们先假设主串遍历到了第九个字符，但是我不知道第9个字符对应的next 数组的数字，我们的第8个字符的上标为8，然后对应的k是2，这里的p[2]是c，说明p[2]和p[8]相等啊，那么。

KMP算法用来找某个字符串是否存在某个连续的真子串的

下面举一个例子让抽象的KMP算法更加直观，有助于理解

首先我们要了解KMP算法首先要找到一个 next 数组来表示主串中每一个字符的回退的下标（这个下标是对于真子串而言的，主串不需要回退）（这可能看的很懵逼，但是不要紧，接着往下看你肯定明白了）

例：寻找字符串”abc ae f abc d absd“的子串 abc d

//str代表主串
//sub代表子串
//pos代表主串开始移动的位置
//我们定义主串第一个字符下标为-1，第二个就为0
//len是主串的长度
void Getnext(char* str, int* next, int len)
{
	next[0] = -1;;//我们定义主串第一个字符对应的next数组第一个元素为-1
	next[1] = 0;//第二个就为0
	//从第三个开始找next数组的规律
	int i = 2;//第三个元素的标号
	int k = 0;
	while (i < len)
	{
		if (k==-1||str[i - 1] == str[k])
		{
			next[i] = k + 1;
			i++;
			k++;
		}
		else
		{
			k = next[k];
		}
	}
}

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h&gt;
#include<string.h&gt;
#include<assert.h&gt;
#include<stdlib.h&gt;
//str代表主串
//sub代表子串
//pos代表主串开始移动的位置
//我们定义主串第一个字符下标为-1，第二个就为0
void Getnext(char* str, int* next, int len)
{
	next[0] = -1;;//我们定义主串第一个字符对应的next数组第一个元素为-1
	next[1] = 0;//第二个就为0
	//从第三个开始找next数组的规律
	int i = 2;//第三个元素的标号
	int k = 0;
	while (i < len)
	{
		if (k==-1||str[i - 1] == str[k])
		{
			next[i] = k + 1;
			i++;
			k++;
		}
		else
		{
			k = next[k];
		}
	}
}
int KMP(char* str,char* sub,int pos)
{
	assert(str&amp;&amp;sub);
	int i = pos;//遍历主串
	int j = 0;//遍历子串
	int lenstr = strlen(str);
	int lensub = strlen(sub);
	//此时都空的字符串
	if (lenstr == 0 || lenstr == 0) return -1;
	//此时如果遍历主串的pos<0或者大于等于主串长度，也是返回-1
	if (pos < 0 || pos &gt;= lenstr) return -1;
	int* next = (int*)malloc(lenstr * sizeof(int));//主串的元素个数和next数组相同
	assert(next);
	Getnext(str,next,lenstr);
	while(i<lenstr&amp;&amp;j<lenstr)
	{
		if (j==-1||str[i] == sub[j])
		{
			i++;
			j++;
		}
		else
		{
			j = next[j];
		}
	}
	//遍历完之后
	if (j &gt;= lensub)
		return i - j;//返回主串找到子串第一个字符的下标
	//如果没有找到返回0
	return 0;
}
int main()
{
	printf("%d", KMP("abdaabc","abc",0));
	return 0;
}

void Getnext(char* str, int* next, int* nextval,int len)
{
	next[0] = -1;;//我们定义主串第一个字符对应的next数组第一个元素为-1
	next[1] = 0;//第二个就为0
	//从第三个开始找next数组的规律
	int i = 2;//第三个元素的标号
	int k = 0;
	while (i < len)
	{
		if (k==-1||str[i - 1] == str[k])
		{
			next[i] = k + 1;
			i++;
			k++;
		}
		else
		{
			k = next[k];
		}
	}
	//开始设计nextval数组
	i = 2;
	nextval[0] = -1;
	nextval[1] = 0;
	while (i < len)
	{
		//相同的话就回退到那一个nextval的值
		if (str[i] == str[next[i]])
		{
			nextval[i] = next[next[i]]; 
			i++;
		}
		//不同的话，就等于next的值
		else
		{
			nextval[i] = next[i];
			i++;
		}
	}
}