KMP 算法的实现详解

作者：lovevivi

2022-10-14
吉林
本文字数：1458 字
阅读完需：约 5 分钟

@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;}