本文共 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个字符的最长前缀和后缀重合的长度。

举例说明：

• next[1] = -1（字符“a”无前后缀重合）。
• next[2] = -1（字符“ab”无前后缀重合）。
• next[3] = 0（字符“aba”中“a”是最长前后缀重合部分）。
• next[4] = 1（字符“abab”中“ab”是最长前后缀重合部分）。
• next[5] = -1（字符“ababc”中无最长前后缀重合）。

注意事项：

如何求前缀函数

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

示例：

• 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算法的主要步骤：

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

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

总结

KMP算法通过预处理文本，建立前缀函数，实现了高效的字符串匹配。其核心思想是“失败后跳退”，避免重复比较，显著提升了匹配效率。掌握KMP算法的读者可以轻松应对更复杂的字符串处理问题。

转载地址：http://dole.baihongyu.com/