KMP算法个人理解

wuchangjian2021-11-03 15:15:13编程学习

KMP算法

核心思想:当模式串失配时,通过失配函数next确定从模式串的那个位置重新匹配,不回溯目标串
其中,失配后如何确定模式串的位置只与模式串本身有关,与目标串无关
代码如下:

#include<iostream>
using namespace std;
typedef char ElemType;
void getnext(ElemType* p, int* next) {//KMP算法只与模式串P有关
  int j = 0;//初始化J为0,此时K等于-1,next[j]为0
  int k = -1;
  next[0] = -1;
  int plen = strlen(p);
  while (j < plen - 1) {//在已知next[0,1,……j]的情况下求next[j+1]!!!!
    if (k == -1 || p[k] == p[j]) {//k=-1时,下一个J为1失配,J之前的最大前后缀重复度为0,显然是K++,J++
      k++;						 //p[k]==p[j]说明在前一个的基础上最大前后缀重复度增加了1
      j++;	
      next[j] = k;				//next[j]的值也就是J失配时0到J-1的最大前后缀重复度
	}
	else {//此时 p[k] != p[j]意味着 下标为k失配,要找从哪个下标开始跟p[j]匹配,也就是令k=next[k],找新的匹配位置,找新的最大前后缀(j=next[j])
      k = next[k];
	}
  }
}
//优化过后的next 数组求法
void GetNextval(char* p, int next[]) {
  int pLen = strlen(p);
  next[0] = -1;
  int k = -1;
  int j = 0;
  while (j < pLen - 1) {
    // p[k]表示前缀,p[j]表示后缀
    if (k == -1 || p[j] == p[k]) {
      ++j;
      ++k;
      //较之前next数组求法,改动在下面4行
      if (p[j] != p[k])
        next[j] = k;  //之前只有这一行
      else
        //因为不能出现p[j] = p[ next[j ]],所以当出现时需要继续递归,k = next[k]
        //= next[next[k]]
        next[j] = next[k];
    } else {
      k = next[k];
    }
  }
}
int KMP(ElemType* S, ElemType* P, int pos) {
  int plen = strlen(P);
  int slen = strlen(S);
  int* next = new int[plen+1];
  getnext(P, next);
  int i = pos - 1, j = 0;
  while (i < slen  && j < plen ) {
    if (j == -1 || S[i] == P[j]) {
      i++;
      j++;
	}
	else {//失配后重新寻找要去配对的下标
      j = next[j];
	}
  }
  if (j == plen)
    return i - plen;
  else {
    return -1;
  }
}

对于改进的失配函数,为什么next[j]等于next[k]能保证,不与失配的p[j]相等我还不太明白,希望有读者能帮我解答

发表评论    

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。