KMP演算法

KMP演算法是一個字串匹配演算法，或者說是一個子字串匹配演算法

演算法在字串str中搜索子串pattern，如果存在，回傳這個子串的起始索引，如果不存在，回傳-1

暴力列舉匹配

暴力的字串匹配演算法非常簡單，就是列舉所有可能的起始索引 i，對于每一個索引，都通過與pattern逐個字符地進行比較來檢查是否匹配，代碼如下：

static int matchString(String str, String pattern) {
  for (int i = 0; i <= str.length() - pattern.length(); ++i) {
      for (int j = 0; j < pattern.length(); ++j) {
          if (str.charAt(i + j) != pattern.charAt(j)) {
              break;
          }
          if (j == pattern.length() - 1) {
              return i;
          }
      }
  }
  return -1;
}

顯而易見，這種演算法在一些比較極端的情況下的運行情況非常不理想

如 str = "aaaabcacbab"，pattern = "aaaac" 時

在 i = 0 時，i 和 j 增加到4發現不匹配
        i
a a a a b c b a b
a a a a c
        j

接著 i 回退到 1，又經過了3次比較發現不匹配
        i
a a a a b c b a b
  a a a a c
        j

顯然做了很多冗余的比較，而KMP就是一種對于這些極端情況也能夠高效處理的演算法

什么是next陣列

在上面的例子中，如果是人進行模擬，在 i = 0 的4次比較發現不匹配后，顯然沒有必要將 i 回退到1，j 回退到0再開始比較，而是可以不回退i，直接從 j = 3 開始比較，

這實際上是由于在第一次的比較中，我們得到了 str[0 ~ 3] = pattern[0 ~ 3] 的資訊，因此，不需要 i 再回退到1去依次訪問和比較 str[1]，str[2]，str[3]，而可以保持 i 不動，通過 pattern 自身的性質讓 j 進行跳轉，繼續進行比較

而對于每一個 j，當出現 str[i] != pattern[j] 時，j 進行跳轉后的下一個位置就是 next[j]

如何計算 next 陣列

首先根據上面的定義，i 和 j 滿足 str[i - j ~ i - 1] = pattern[0 ~ j - 1], 將 next[j] 暫時記為 k，i 和 k 要滿足 str[i - k ~ i] = pattern[0 ~ k - 1]

這樣一看，j 和 k 豈不是相等的？那是因為還少了幾個約束，首先，由于 i 和 j 取舊的值時已經確定不能匹配，因此 k（即新的 j）的值不能和j相等，而如果有 k > j 滿足 str[i - k ~ i] = pattern[0 ~ k -1]，在之前一定被處理過，因此，k 一定會小于 j，并且，為了不漏過可能的子串，k 應該是滿足條件的最大值

那么，根據 str[i - j ~ i - 1] = pattern[0 ~ j - 1]，可以得到 str[i - k ~ i - 1] = pattern[j - k ~ j - 1]

再根據 str[i - k ~ i - 1] = pattern[0 ~ k - 1]，得到 pattern[0 ~ k - 1] = pattern[j - k ~ j - 1]

也就是說，對于每一個 j，k = next[j] 是滿足 pattern[0 ~ k - 1] = pattern[j - k ~ j - 1]的最大的k，直觀來描述，就是在j之前的串中，前 k 個位置和后 k 個位置相同，k的最大值

我們把在一個字串中前 k 個位置和后 k 個位置相同，k的最大值記為字串的 X 長度，相同的前 k 個位置和后 k 個位置記為 X 前綴和 X 后綴

要求滿足條件的 k，就只需要考慮pattern了，首先考慮 k 和 next[j - 1]的關系，t = next[j - 1]是滿足 pattern[0 ~ t - 1] = pattern[j - 1 - t ~ j - 2] 的最大值，就是j - 1之前的串的 X 長度，顯然，當 pattern[j - 1] = pattern[t] 時，k = t + 1

那么當 pattern[j - 1] ！= pattern[t]的時候呢，可以通過向前迭代 t 來繼續進行比較，令 t = next[t]，如果 pattern[j - 1] = pattern[t] 時，k = t + 1，如果不等，則繼續迭代，令 t = next[t]

上面的迭代為什么是正確的呢，因為當 pattern[j - 1] ！= pattern[t] 時，我們考慮 j - 1 之前的串的 X 后綴的 X 前綴和 X 后綴，j - 1之前的串的 X 前綴的 X 前綴和 j - 1 之前的串的 X 后綴的X 后綴是相等的，又因為 X 的最長特性，顯然是下一個檢查的物件，也就是令 t = next[t] 進行迭代，這樣的迭代可以通過遞回來考慮，終止條件就是當 t 迭代到 0 的時候

X 前綴
--------- t           j - 1
XXX***XXX   XXX***XXX
            ---------
            X 后綴
//X 前綴中***部分第一個位置即為 next[t]

結合上面的演算法，考慮一些邊界情況，最終寫出代碼如下:

static int matchString(String str, String pattern) {
  if (str.length() < pattern.length() || str.isEmpty()) {
      return -1;
  }
  int[] next = new int[pattern.length()];
  //計算next陣列的值
  next[0] = -1;
  for (int i = 1; i < next.length; ++i) {
      int k = i - 1;
      while (k > 0 && pattern.charAt(i - 1) != pattern.charAt(next[k])) {
          k = next[k];
      }
      next[i] = next[k] + 1;
  }
  //進行匹配
  int i = 0, j = 0;
  while (i < str.length()) {
      while (i < str.length() && str.charAt(i) == pattern.charAt(j)) {
          i++;
          j++;
          if (j == pattern.length()) {
              return i - j;
          }
      }
      j = next[j];
      //終止條件，j 需要移動到 pattern 的第一個位置，那么 i 就需要向后移動一位
      if (j < 0) {
          j = 0;
          i++;
      }
  }
  return -1;
}

標籤：其他

上一篇：寶塔面板發布vue頁面

下一篇：KMP演算法