---
title: KMP algorithm
tags: Algorithms
---

## 前言

今天要介紹的Knuth-Morris-Pratt algorithm(簡稱KMP algorithm)，是在1974年由這三位大師發明的字串搜尋演算法，專門用來解決以下的問題。

## 問題

給定字串$a$和字串$b$，求$b$是否有出現在$a$當中($b$是否是$a$的子字串)，以及出現的位置。

舉例來說，$a = "yodayo", b = "yo"$，那麼我們會說$b$出現在$a$中$[0, 1]$以及$[4, 5]$的位置。

實際應用的話，瀏覽器的“尋找”功能就是在解決這個問題喔～

## brute-force algorithm

很顯然地，我們可以把$a$的第一個字元跟$b$的第一個字元對齊，然後檢查$a_0 = b_0, a_1 = b_1, a_2 = b_2...$，如果途中有字元不相同，那就把$b$的第一個字元對齊$a$的下一個字元，再比對一次; 如果所有字元都相同，就代表我們找到其中一個答案了。

用C++來寫的話，大概長這樣

void matching(string &a, string &b) {
  for(int i = 0; i + b.size() - 1 < a.size(); i++) {
    bool matched = true;
    for(int j = 0; j < b.size(); j++) {
      if (a[i + j] != b[j]) {
        matched = false;
        break;
      }
    }

    if (matched) {
      cout << "found a match start at position " << i << endl;
    }
  }
}

input: 
    a = "abbacabbab", b = "abbab"
result:
    found a match start at position 5

用圖來表示的話，大概長這樣(前四輪比對)。


這種演算法的期望時間複雜度是$O(n)$，最差狀況的時間複雜度是$O(nm)(n = a.size, m = b.size)$。也就是說在平常$a$和$b$沒有經過特別設計的狀況下，複雜度其實是不錯的，但是在某些特定的case會變得跑很慢。

## KMP algorithm

#### 改良

稍微觀察上面那張圖。在第一輪比對時，我們已經掃過$a[0, 4]$，但是下一輪的時候，我們又回去掃$a[1]$，而$a[1]$應該是我們早該知道的資訊，但是卻沒有完善的利用。或許我們能針對已知的資訊做一些改良？

再用力一點觀察，究竟有甚麼已知的資訊我們沒有善加利用呢？透過第一輪比對時，我們得知$a[0, 3] = b[0, 3], a[4] \ne b[4]$，而在第二輪的比對時，我們想知道$a[1, 5] = b[0, 4]$究竟有沒有成立。
利用我們已知的資訊，我們可以把它變成$b[1, 3] + a[4, 5] = b[0, 4]$有沒有成立，也就是說，如果$b[1, 3] \ne b[0, 4]$，那第二輪比對根本不需要做，因為它不可能比對成功！

不失一般性，我們考慮在$b[i + 1]$的時候配對失敗，那下一次的配對如果將$b$字串往右移動$s$格的話，首先要滿足$b[0, i - s] = b[s, i]$，才有可能配對成功。而這個條件在做的事情正是拿$b[0, i]$的後綴跟$b$的前綴做比對。如果可以預處理對於每個$b[i]$配對失敗時，滿足以上條件的$s$最小是多少，那我們就可以知道每次配對失敗時，最少要往右移動幾格才有可能成功配對。


#### fail function

因此我們有了以下稱作“失配函數“的東西。
$$F(i) =
\begin{cases}
max\{k: b[0, k] = b[i - k, i] \text{ and } k < i\} &\quad \text{if k exist}
\\
-1 &\quad else
\end{cases}
$$

其中$F(i)$就代表在$i + 1$失配時，$b[0, i]$的後綴和$b$的前綴中，最長且相同的子字串為$b[0, F(i)]$。
有了這個失配函數之後，每次我們遇到$b[i + 1]$失配的狀況時，我們就可以把$b[F(i)]$對齊到原本$b[i]$的位置！(就是把$b$往右移動時，第一個滿足配對成功前提的對齊方法。)

#### construct fail function

那現在唯一的問題就剩下該怎麼快速地求失配函數了。

首先根據定義，$F(0) = -1$。接下來我們依序求$F(i)(1 \le i < b.size)$。
我們想要求$F(i)$，也就是$b[0, i]$的後綴和$b$的前綴中相同且最長的那一個子字串。
如果這個子字串$b[i - F(i), i] = b[0, F(i)]$長度大於$1$，那他也會滿足$b[i - F(i), i - 1] = b[0, F(i) - 1]$，代表如果把它的最後一個字元拔掉，那他會是$b[0, i - 1]$的某個後綴，也是$b$的某個前綴。

而其中最長的可能就是$b[i - 1 - F(i - 1), i - 1] = b[0, F(i - 1)]$，因此可以拿$b[i]$和$b[F(i - 1) + 1]$(剛剛“拔掉”的字元)做比對，如果相同，我們就找到最長的$b[0, i]$後綴等於$b$前綴，並且$F(i) = F(i - 1) + 1$。

那如果不同呢？那代表我們要找一個次次長的$b[0, i - 1]$後綴等於$b$前綴。
再仔細觀察失配函數的定義，會發現其實$F(x)$就是在找$b[0, x]$後綴等於$b$前綴中，滿足條件的“次長”子字串(最長的是$b[0, x] = b[0, x]$)。所以如果我們要找的次次長的子字串，其實就是$b[0, F(F(i - 1))]$(次長是$b[0, F(i)]$)，因此我們只要檢查$b[i]$和$b[F(F(i - 1)) + 1]$是否相同即可，再不同就檢查$b[F(F(F(i - 1)))]$...，直到其值為$-1$，如果$b[-1 + 1] = b[i]$，$F(i) = -1 + 1$，反之不存在滿足條件的字串，$F(i) = -1$。

最後的最後，如果這個子字串$b[i - F(i), i] = b[0, F(i)]$長度等於$1$呢？
其實他已經在上一段的最後一個操作cover到了，所以不用擔心！
(這一段看到一坨代數可能會腦袋燒雞，建議自己畫圖作輔助會比較好瞭解)

#### implementation

既然理論已完備，就剩下實作了，其實實作意外的簡單？

vector<int> f;
void buildFailFunction(string &s) {
  f.resize(s.size(), -1);
  for(int i = 1; i < s.size(); i++) {
    int now = f[i - 1];
    while(now != -1 and s[now + 1] != s[i]) now = f[now];
    if (s[now + 1] == s[i]) f[i] = now + 1;
  }
}

void KMPmatching(string &a, string &b) {
  for(int i = 0, now = -1; i < a.size(); i++) {
    while (a[i] != b[now + 1] and now != -1) now = f[now];  
    if (a[i] == b[now + 1]) now++;
    if (now + 1 == b.size()) {
      cout << "found a match start at position " << i - now << endl;
      now = f[now];
    }
  }
}

至於複雜度的估計，觀察到$now$指針後退的次數不會多於$i$前進的次數，因此時間複雜度是$O(n + m)(n = a.size, m = b.size)$。