Inhzus

Tech blog of inhzus.

KMP 算法回顾

2019-02-06


记得系统学习 KMP 算法的时候是在大二的算法课上, 当时印象中掌握的是不错的, 不过时隔一年, 遇到 leetcode implement-strstr 一题需要用到 KMP 时, 居然理解上有些困难. 在这里回顾一下实现的重点.

搜索代码

int KmpSearch(char *s, char *p) {
  int i = 0;
  int j = 0;
  int sLen = strlen(s);
  int pLen = strlen(p);
  while (i < sLen && j < pLen) {
    // 如果j = -1, 或者当前字符匹配成功(即S[i] == P[j]), 都令i++, j++
    if (j == -1 || s[i] == p[j]) {
      i++;
      j++;
    } else {
      // 如果j != -1, 且当前字符匹配失败(即S[i] != P[j]), 则令 i 不变, j = next[j]
      // next[j]即为j所对应的next值
      j = next[j];
    }
  }
  if (j == pLen)
    return i - j;
  else
    return -1;
}

next 数组

算法的核心在于, next 数组的意义

匹配字符最大前缀后缀公共元素长度
a0
b0
a1
b2

next 数组值为相应值 - 1

匹配字符next
a-1
b0
a0
b1

计算 next 数组

最关键的问题在于为什么要递归前缀索引 k = next[k], 这一过程相当于模式的自我匹配. 不断地向前递归进行匹配, 直到成功.

由此有代码

void GetNext(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]) {
      ++k;
      ++j;
      next[j] = k;
    } else {
      k = next[k];
    }
  }
}  

不过这个代码的问题在于, 当匹配失败时, 递归到 p[next[k]] 时, p[next[k]] 和 p[k] 仍很有可能相同, 如下图

匹配字符jnext
a0-1
b10
c20
d30
a40
b51
d62

可见, p[5] == p[next[5]], p[4] == p[next[4]].

由此可优化, 当相等时, 可令 next[j] = next[next[j]], 减少了在 KMP 搜索时的递归.

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

以上是对 从头到尾彻底理解KMP 的自我理解.