深入浅出：KMP算法最！详！解！-白红宇

深入浅出：KMP算法最！详！解！

阅读量：349 次

发布时间：2019-03-04

本文共 1701 字，大约阅读时间需要 5 分钟。

KMP算法详解

KMP算法是字符串匹配领域的经典算法，由Knuth、Morris和Pratt三位学者联合提出。它通过预处理文本信息，显著提升了字符串匹配的效率。以下将从基础到应用，详细讲解KMP算法的工作原理及其实现。

什么是KMP算法

传统的字符串匹配算法（如暴力搜索）时间复杂度为O(n*m)，在处理大规模文本时效率极低。KMP算法通过预处理文本，建立一个叫做“前缀函数”（Prefix Function）的数组，来优化匹配过程。

优点：

时间复杂度降至O(n + m)，大大提高了匹配效率。

空间复杂度同样为O(n)，实现简单且内存占用低。

前缀函数（Prefix Function）的含义

前缀函数是一个数组next[i]，其中next[i]表示字符串前i个字符的最长前缀，同时也是后缀最长的相同部分。具体规则如下：

next[0] = -1（无前缀可用）。

next[i]表示前i个字符的最长前缀和后缀重合的长度。

举例说明：

字符串“ababc”，其前缀函数为：

next[1] = -1（字符“a”无前后缀重合）。

next[2] = -1（字符“ab”无前后缀重合）。

next[3] = 0（字符“aba”中“a”是最长前后缀重合部分）。

next[4] = 1（字符“abab”中“ab”是最长前后缀重合部分）。

next[5] = -1（字符“ababc”中无最长前后缀重合）。

注意事项：

“kkkk”的最长前后缀重合长度为3，而不是4。

在“aba”中，“ab”和“ba”不算作最长前后缀重合。

如何求前缀函数

前缀函数的建立是KMP算法的核心步骤，实现方式如下：

初始化next数组，所有元素初始为-1。

从左到右逐个字符处理字符串，维护当前匹配的最大长度k。

对于每个字符str[i]，如果与当前匹配字符串的下一个字符（即str[k+1]）相同，k+1。

如果不相同，则将k设置为next[k]，并重复步骤3，直到k = -1。

记录当前k值为next[i]。

示例：

字符串“abcabcab”

i=0时，k=-1，next[0]=-1。

i=1时，k=0，且字符“a”与“b”不同，k=next[-1]=-1。

i=2时，k=0，字符“b”与“c”不同，k=next[-1]=-1。

i=3时，k=0，字符“c”与“a”不同，k=next[-1]=-1。

i=4时，k=0，字符“a”与“b”不同，k=next[-1]=-1。

继续匹配，直到所有字符处理完毕。

KMP算法实现

KMP算法的核心是利用前缀函数实现高效匹配。以下是KMP算法的主要步骤：

预处理阶段：

初始化next数组，设置next[0] = -1。

通过逐字符匹配，填充next数组。

匹配阶段：

初始化k = 0，表示当前匹配的字符数。

从字符串的第一个字符开始，逐个字符比较。

如果字符匹配，k++。

如果不匹配，k = next[k]，并继续匹配。

当k = next数组长度时，表示找到匹配，记录结果并重置k = next[k]。

代码示例（字符数组版）：

void kmp() {      find_next();      int k = 0;      for (int i = 1; i <= len; i++) {          while (k > 0 && mbs[k+1] != ys[i]) {              k = next[k];          }          if (mbs[k+1] == ys[i]) {              k++;          }          if (k == len) {              ans++;              k = next[k];          }      }  }