KMP算法也是一种解决字符串匹配问题的算法，它的中心思想是：尽可能的减少匹配次数。

一、KMP算法原理探究

以此图为例：

截屏2020-04-25下午7.55.51.png

二、next数组值推导

我们把子串各个位置 j 值变化定义为一个 next 数组，那么next 的长度就是 子串的长度

截屏2020-04-25下午8.38.26.png

截屏2020-04-25下午8.32.12.png

• 当j=1时，next[1]=0
• 当 j=2时, j 由 1到 j-1 范围内只有字符 “a”, 属于其他情况 next[2] = 1
• 当 j=3时, j 由 1到 j-1 范围内有字符 “ab”,显然 a 不等于 b, 属于其他情况 next[3] = 1
• 当 j=4时, j 由 1到 j-1 范围内有字符 ”aba”, 显然”aba”, 前缀字符 “a” 与 后缀字符 ”a” 相等,所以 k = 2; next[4] = 2
• 当 j=5时, j 由 1到 j-1 范围内有字符 ”abab”, 显然”abab”, 前缀字符 “ab” 与 后缀字 符 ”ab” 相等,所以 k = 3; next[5] = 3
• 当 j=6时, j 由 1到 j-1 范围内有字符 “ababa”,前缀 “aba” 与 后缀 “aba” 相等,那么此时 k = 4; next[6] = 4
• 当 j=7时, j 由 1到 j-1 范围内有字符 “ababaa”,前缀 “a” 与 后缀 “a” 相等,那么此时 k = 2; next[7] = 2
• 当 j=8时, j 由 1到 j-1 范围内有字符 “ababaaa”,前缀 “a” 与 后缀 “a” 相等,那么此时 k = 2; next[8] = 2
• 当 j=9时, j 由 1到 j-1 范围内有字符 “ababaaab”,前缀 “ab” 与 后缀 “ab” 相等,那么此时 k = 3; next[9] = 3

三、KPM函数实现

生成一个S[0]为字符串长度的字符串S

Status strAssign(String S,char *c){
  
  if (strlen(c)>MAXSIZE) {
      return ERROR;
  }else{
      S[0] = strlen©;
      for (int i = 1; i<=S[0]; i++) {
          S[i] = c[i-1];
      }
  }
  return OK;
}

打印字符串S

void stringPrint(String S){
  for (int i = 1; i<=S[0]; i++) {
      printf("%c",S[i]);
  }
  printf("\n");
}

返回串的元素个数

int strLength(String S)
{
  return S[0];
}

获取子串的next数组

void getNext(String S, int *next){
  if (S[0]==0 || S == NULL) {
      return;
  }
  next[1] = 0;
  int j = 1;
  int i = 0;
  while (j<S[0]) {
      if (i == 0|| S[i] == S[j]) {
          i++;
          j++;
          next[j] = i;
      }else{
          i = next[i];
      }
  }
}

输出Next数组值

void nextPrint(int next[],int length)
{
  int I;
  for(i=1;i<=length;i++)
      printf("%d",next[i]);
  printf("\n");
}

KMP匹配算法

int index_KMP(String S, String T){
  int i = 1;
  int j = 1;
  int next[T[0]+1];
  getNext(T, next);
  while (i<=S[0] && j<=T[0]) {
      if (j==0||S[i]==T[j]) {
          i++;
          j++;
      }else{
          j = next[j];
      }
  }
  
  if (j > T[0]) {
      return i-T[0];
  }else{
      return -1;
  }
}  

四、next数组的优化

假设, 主串S = “aaaabcde” ; 模式串 T = “aaaaax”，此时next数组为[0,1,2,3,4,5],当i=5时匹配失败，此时根据j=next[j],j将回溯到4，再次匹配，j继续依次回溯到3、2、1，此时可以看出j从4到1的回溯比较是较为多余的。
那是否可以通过next数组的优化，继续减少匹配的次数？当然是可以的。

截屏2020-04-25下午9.59.36.png

• 当 j = 1, nextVal = 0
• 当 j = 2, 因为第2个字符 “b” 的值next 值是1,而且第一个字符是”a”. 不相等. 所以 nextVal[2] = next[2] = 1
• 当 j = 3, 因为第3个字符”a” 的next 值是1, 所以与第1位的”a”比较得知它们相等, 所以 nextval[3] = nextval[1] = 0
• 当 j = 4, 因为第4个字符”b” 的next 值是2, 所以与第2位的”b”比较得知它们相等, 所以 nextval[4] = nextval[2] = 1
• 当 j = 5 时,next 值为3 , 第5个字符”a” 与第3个字符”a” 相等,则nextVal[5] = nextVal[3] = 0
• 当 j = 6 时,next 值为4 , 第6个字符”a” 与第4个字符”b” 不相等,则nextVal[6] = 4
• 当 j = 7 时,next 值为2 , 第7个字符”a” 与第2个字符”b” 不相等,则nextVal[7] = 2
• 当 j = 8 时,next 值为2 , 第8个字符”b” 与第2个字符”b” 相等,则nextVal[6] = nextVal[2] = 1
• 当 j = 9 时, next 值为3, 第9个字符”a” 与第3个字符”a” 相等,则nextVal[9] = nextVal[3]

代码实现
获取子串的next优化数组

void getNext2(String S, int *next){
  if (S[0]==0 || S == NULL) {
      return;
  }
  next[1] = 0;
  int j = 1;
  int i = 0;
  while (j<S[0]) {
      if (i == 0|| S[i] == S[j]) {
          i++;
          j++;
          if (S[j] == S[i]) {
              next[j] = next[i];
          }else{
              next[j] = i;
          }
      }else{
          i = next[i];
      }
  }
}

demo