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)。