KMP算法的本质

KMP算法本质上是实现了对自动机的模拟。它通过构造一个有限自动机来搜寻某给定的模式在正文中出现的位置。整个算法的核心就是对自动机的构建（或前缀函数的构建，KMP算法不用计算变迁函数，而是根据模式预先计算出一个辅助函数next来实现更快速的状态切换），当完成有限自动机的构建之后对主串的搜寻就显得很简单了。

前缀函数的C/C++代码实现如下：

  1. void prefix_function(char *p, int *next)
  2. {
  3.     int j, k;
  4.     next[0] = -1;
  5.     j = 0; k = -1;
  6.     int length = strlen(p) - 1; // next[0] 已不用计算
  7.     while (j < length) {
  8.         if (k == -1 || p[j] == p[k]) {
  9.             next[j+1] = k + 1;
  10.             k++;
  11.             j++;
  12.         }
  13.         else {
  14.             k = next[k];
  15.         }
  16.     }
  17. }

KMP算法的实现

当next函数求出来之后，再在主串上搜寻模式串就相对简单了，整个过程和朴素的模式匹配算法差不多，C/C++代码实现如下：

  1. int kmp_matching(char *t, char *p)
  2. {
  3.     int t_len = strlen(t);
  4.     int p_len = strlen(p);
  5.  
  6.     // 先预先求出next函数
  7.     int *next = new int[t_len];
  8.     prefix_function(p, next);
  9.  
  10.     int i, j;
  11.     i = 0; j = 0;
  12.     while (i < t_len && j < p_len) {
  13.         if (j == -1 || t[i] == p[j]) {
  14.             i++;
  15.             j++;
  16.         }
  17.         else {
  18.             j = next[j];
  19.         }
  20.     }
  21.  
  22.     if (next != NULL) {
  23.         delete[] next;
  24.         next  = NULL;
  25.     }
  26.  
  27.     if (j == p_len)
  28.         return i - p_len;
  29.  
  30.     return -1;
  31. }

时间复杂度分析

由于KMP算法构造了一个自动机来匹配模式串，因此其主串中的每个字符只需比较一次，并且每个字符比较的时间为常数，所以其时间复杂度为线性。m长度的主串比较时间为O(m)。而前缀函数由于是提前构建，用平摊分析方法可知n长度的模式花费的时间为O(n)，所以KMP算法总的时间复杂度为O(m+n)。