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]相等我还不太明白，希望有读者能帮我解答