KMP算法—终于全部弄懂了,算法 kmp
Yyds干货库存
@TOC
1.KMP算法
KMP是一种改进的字符串匹配算法。该算法的核心是利用匹配失败后的信息，最小化模式串与主串的匹配次数，达到快速匹配的目的。实现是通过next()函数实现的，它包含模式字符串的本地匹配信息。
2.与BF(蛮力算法)的区别
暴力算法：模拟实现strstr函数
当信息匹配失败时，主串I不会回滚，子串J不会回零。
1.j的撤退位置
下标为5时，信息匹配失败。这个时候我就不回去了，这里匹配失败，也就是说在下标为5之前，主串I和子串J的某些部分必须相同。此时J会回到下标为2的位置，然后匹配成功。
2 .下一个数组
接下来[j]=k，不同的j对应k的一个值，k是要移动的j将要移动的位置。
寻找k法则：
1.匹配成功部分的两个相等的真子串(不包括它们自己)，其中一个以后面的0开始，另一个以j-1下标结束。
2.规定next [0]=-1，next [1]=0，形式计算从下标2开始。
3.3 .下一个数组的练习
1.练习1
2.练习2
一个小细节：一般来说，下一个数组下标只会被一个接一个地相加或者赋给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]对应的下一个下标数
4.代码实现
#define _CRT_SECURE_NO_WARNINGS
#包含stdio.h
#包含字符串. h
#include assert.h
#包含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==-1sub[i-1]==sub[k])//当k==-1时，第一个数字不满足条件，进入循环后下一个[i]将被设置为0。
next[I]=k 1；
我；
k；
其他
k=下一个[k]；
KMP整数(字符*字符串，字符*子字符，整数位置)
断言(str！=NULL sub！=NULL)；
int i=pos
int j=0；
int lenstr=strlen(str)；//主字符串的长度
int len sub=strlen(sub)；//子串长度
int * next=(int *)malloc(sizeof(int)* len sub)；
断言(下一个！=NULL)；
getnext(sub，next，len sub)；
while (i lenstr j lensub)
If (j==-1str[i]==sub[j])//当一个数不满足条件时，此时需要添加一个条件，否则会造成越界。
我；
j；
其他
j=next[j]；
if (j=lensub)
返回I-j；
return-1；
int main()
char S1[40]；
char S2[40]；
scanf(%s%s ，s1，S2)；
printf(%d\n ，KMP(s1，s2，0))；
返回0；
1.代码注意事项
1.当1.next数组值为-1时
这个时候的P[i]！=p[k]时，下一个数组的值总是返回到前一个p，但直到第一个数还是p[i]！=p[k]，
K会被设置为-1，进入if循环后，K的值为0，也就是next在这个位置的下标为0。
2.当k的值为-1时
只有第一个数字对应的下一个数组的值为-1，表示主串和子串的第一个数字匹配信息失败。
在if循环中，如果不加j==-1的判断，只加sub[i]==sub[j]，会导致出界。
。
郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。