“我报名参与金石方案1期挑战——瓜分10万奖池，这是我的第2篇文章，点击查看活动详情”

@TOC

1.KMP算法

1.概念

KMP是一种改进的字符串匹配算法，该算法的中心是利用匹配失败后的信息，尽量减少形式串与主串的匹配次数以达到快速匹配的意图。 具体完成经过一个next()函数完成，函数本身包含了形式串的局部匹配信息。

2.与BF(暴力算法)的的差异

暴力算法:模拟完成strstr函数 当信息匹配失败时，主串i不会回退，子串j也不会回到0号方位

3.分析

1.j的回退方位

在下标为5时，信息匹配失败，此刻i不回退，在此匹配失败，阐明 主串i与子串j下标5之前一定有一部分是相同的，此刻j回退到 下标为2的方位，持续向后就能匹配成功。

2.next数组

next[j]=k来表明，不同的 j 对应一个k值，k为要移动的 j 要移动的方位

寻觅k规矩： 1.匹配成功部分的两个持平的真子串(不包含本身)，一个以下标0开始，另一个以j-1下标开始结束。 2.规定 next[0]=-1 ,next[1]=0, 正式计算是从下标2开始。

3.next数组的练习

1.练习1

注意事项

2.练习2

注意事项

一个小细节：一般来说next数组下标 只会一个一个数加 或者被赋值成0

4.推导过程

在next[i]=k的前提下

1.p[i]==p[k]

在p[0]……p[k-1] p[i-k]==p[i-1] ， next[i]=k的前提下 ….p[0]……p[k-1] p[k] == p[x]…p[i-1] p[i] ， next[i+1]=k+1

2.p[i]!=p[k]

回退到下标为2的方位，发现此刻p[i]!=p[k]，则从当时方位持续回退， 直到p[i]==p[k]，再经过next[i+1]=p[k+1]， 确定p[i+1]对应的next下标数

4.代码完成

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<string.h>
#include<assert.h>
#include<stdlib.h>
//str代表主串
//sub代表子串
//pos代表从当时方位
void getnext(char* sub,int*next,int lensub)
{
	next[0] = -1;
	next[1] = 0;
	int i = 2;//下一项
	int k = 0;//前一项的k
	while (i < lensub)
	{
		if (k==-1||sub[i - 1] == sub[k])//当k==-1时，阐明榜首个数不符合条件，进入循环后next[i]会被置成0
		{
			next[i] = k + 1;
			i++;
			k++;
		}
		else
		{
			k = next[k];
		}
	}
}
int KMP(char* str, char* sub, int pos)
{
	assert(str != NULL && sub != NULL);
	int i = pos;
	int j = 0;
	int lenstr = strlen(str);//主串长度
	int lensub = strlen(sub);//子串长度
	int* next = (int*)malloc(sizeof(int) * lensub);
	assert(next != NULL);
	getnext(sub,next, lensub);
	while (i < lenstr && j < lensub)
	{
		if (j==-1||str[i] == sub[j])//当一个数不符合条件时,此刻就需要参加一个条件，不然就会形成越界
		{
			i++;
			j++;
		}
		else
		{
			j = next[j];
		}
	}
	if (j >= lensub)
	{
		return i - j;
	}
	return -1;
}
int main()
{
	char s1[40];
	char s2[40];
	scanf("%s%s", s1, s2);
	printf("%d\n", KMP(s1,s2,0));
	return 0;
}

1.代码的注意事项

1.next数组值为-1时

当此刻的p[i]!=p[k]时，一直经过next数组值返回到前面的p地点，但到榜首个数仍旧p[i]!=p[k]时， 则会将k置成-1，进入if循环后 k值为0 即 此方位的next地点下标为0

2.k值为-1时

只要榜首个数对应next数组的值为-1，阐明主串与子串榜首个数就信息匹配失败 而在if循环中假如不参加j==-1的判别 ,只要 sub[i]==sub[j]，则会形成越界

2.KMP算法的优化

关于next数组的优化

若在下标为5的方位信息匹配失败，就会一直回退，直到下标为0的方位 优化的意图就会使 此刻直接找到下标为0的方位

1.规矩

假如回退到的方位和当时字符一样，就写回退那个方位的nextval值 假如回退到方位和当时字符不一样，就写当时字符原来的nextval值

2.练习题