【模式匹配】KMP算法的來龍去脈

1. 引言

字符串匹配是極為常見的一種模式匹配。簡單地說，就是判斷主串 \(T\) 中是否出現該模式串 \(P\) ，即 \(P\) 為 \(T\) 的子串。特別地，定義主串為 \(T[0 \dots n-1]\) ，模式串為 \(P[0 \dots p-1]\) ，則主串與模式串的長度各為 \(n\) 與 \(p\) 。

2. 匹配算法

先介紹暴力（brute-force）匹配的方法，然后根據暴力方法的缺點而引出KMP算法的思想，接著介紹如何計算部分匹配函數（Partial Match）與next函數的計算。

暴力方法

暴力匹配方法的思想非常樸素：

1. 依次從主串的首字符開始，與模式串逐一進行匹配；
2. 遇到失配時，則移到主串的第二個字符，將其與模式串首字符比較，逐一進行匹配；
3. 重復上述步驟，直至能匹配上，或剩下主串的長度不足以進行匹配。

下圖給出了暴力匹配的例子，主串 T="ababcabcacbab" ，模式串 P="abcac" ，第一次匹配：

第二次匹配：

第三次匹配：

C代碼實現：

int brute_force_match(char *t, char *p) {
    int i, j, tem;
    int tlen = strlen(t), plen = strlen(p);
    for(i = 0, j = 0; i <= tlen - plen; i++, j = 0) {
        tem = i;
        while(t[tem] == p[j] & j < plen) {
            tem++;
            j++;
        }
        // matched
        if(j == plen) {
            return i;
        }
    }
    // [p] is not a substring of [t]
    return -1;
}

時間復雜度： i 在主串移動次數（外層的for循環）有 \(n-p\) 次，在失配時 j 移動次數最多有 \(p-1\) 次（最壞情況下）；因此，復雜度為 \(O(n*p)\) 。

我們仔細觀察暴力匹配方法，發現：失配后下一次匹配，

• 主串的起始位置 = 上一輪匹配的起始位置 + 1；
• 模式串的起始位置 = 首字符 P[0] 。

如此未能利用已經匹配上的字符的信息，就造成了 重復匹配 。舉個例子，比如：第一次匹配失敗時，主串、模式串失配位置的字符分別為 a 與 c ，下一次匹配時主串、模式串的起始位置分別為 T[1] 與 P[0] ；因為在模式串中 c 之前是 ab ，未有 重復的字符結構 ，因此 T[1] 與 P[0] 肯定不能匹配上，這樣造成了重復匹配。直觀上，下一次的匹配應從 T[2] 與 P[0] 開始。

KMP思想

首先，來看第一次匹配失敗，如下圖所示：

從圖中可以看出，已匹配上的字符滿足：

\[ T[i \dots i+j-1] = P[0 \dots j-1] \]

KMP算法思想：利用已經匹配上的字符信息，在下一次的匹配時，將已經匹配上的字符結構重新對齊，置下一次匹配

• 主串的起始位置 = 上一輪匹配的失配位置；
• 模式串的起始位置 = 重復字符結構的下一位字符

如下圖所示：

從圖中得到模式串的重復字符結構：

且有

\[ T[i+j] \neq P[j] \neq P[m+1] \]

那么應如何選取 \(m\) 值呢？假定有滿足式子\eqref{eq:overlap}的兩個值 \(m_1 > m_2\) ，如下圖所示：

如果選取 \(m=m_2\) ，則會丟失 \(m=m_1\) 的這一種字符匹配情況。由數學歸納法容易知道， \(m\) 值應為滿足式子\eqref{eq:overlap}中最大的那一個。

模式串 P="abcac" 匹配主串 T="ababcabcacbab" 的KMP過程如下圖：

部分匹配函數

根據上面的討論，我們定義部分匹配函數（Partial Match，在數據結構書[2]稱之為失配函數）：

\[ f(j) = \left\{ {\matrix{ {\max \{ m \} } & P[0\dots m]=P[{j-m}\dots {j}],0\le m < j \cr {-1} & else \cr } } \right. \]

失配函數表示模式串中重復字符結構信息。KMP中大名鼎鼎的 next[j] 函數表示對于模式串失配位置為 j+1 ，下一輪匹配時模式串的起始位置（即對齊于主串的失配位置）；則有

\[ next[j] = f(j)+1 \]

如何計算部分匹配函數呢？首先來看一個例子，模式串 P="ababababca" 的部分匹配函數與next函數如下：

模式串的 f(j) 滿足 \(P[0 \dots f(j)]=P[j-f(j) \dots j]\) ，在計算 f(j+1) 分為兩類情況：

• 若 \(P[j+1]=P[f(j)+1]\) ，則有 \(P[0 \dots f(j)+1]=P[j-f(j) \dots j+1]\) ，因此 f(j+1)=f(j)+1 。
• 若 \(P[j+1] \neq P[f(j)+1]\) ，則要從 \(P[0 \dots f(j)]\) 中找出滿足 P[f(j+1)]=P[j+1] 的 f(j+1) ，從而得到 \(P[0 \dots f(j+1)]=P[j+1-f(j+1) \dots j+1]\)

其中，根據 f(j) 的定義有：

\[ P[j]=P[f(j)]=P[f(f(j))]=\cdots = P[f^k(j)] \]

其中， \(f^k(j)=f(f^{k-1}(j))\) 。通過上面的例子可知，函數 \(f^k(j)\) 是隨著 \(k\) 遞減的，并最后收斂于 -1 。此外， P[j] 與 p[j+1] 相鄰；因此若存在 P[f(j+1)]=P[j+1] ，則必有

\[ f(j+1)=f^k(j)+1 \]

為了求滿足條件的最大的 f(j+1) ，因 \(f^k(j)\) 是隨著 \(k\) 遞減的，故應求滿足上式的最小 \(k\) 值。

總結部分匹配函數的計算分析如下：

\[ f(j) = \left\{ {\matrix{ {f^k(j-1)+1} & \min \limits_{k} P[f^k(j-1)+1]=P[j] \cr {-1} & else \cr } } \right. \]

代碼實現

部分匹配函數（失配函數）的C實現代碼：

int *fail(char *p) {
    int len = strlen(p);
    int *f = (int *) malloc(len * sizeof(int));
    f[0] = -1;
    int i, j;
    for(j = 1; j < len; j++) {
        for(i = f[j-1]; ; i = f[i]) {
            if(p[j] == p[i+1]) {
                f[j] = i + 1;
                break;
            }
            else if(i == -1) {
                f[j] = -1;
                break;
            }
        }
    }
    return f;
}

KMP的C實現代碼：

int kmp(char *t, char *p) {
    int *f = fail(p);
    int i, j;
    for(i = 0, j = 0; i < strlen(t) && j < strlen(p); ) {
        if(t[i] == p[j]) {
            i++;
            j++;
        }
        else if(j == 0)
            i++;
        else
            j = f[j-1] + 1;
    }
    return j == strlen(p) ? i - strlen(p) : -1;
}

時間復雜度： fail 函數的復雜度為 \(O(p)\) ， kmp 函數的復雜度為 \(O(n)\) ，所以整個KMP算法的復雜度為 \(O(n+p)\) 。

3. 參考資料