算法—KMP算法

算法—KMP算法 1. 简介

KMP 算法是一个时间复杂度为 O ( m + n ) O(m+n) O(m+n) 的字符串匹配算法，其中， n n n 为文本串长度， m m m 为模式串长度。

设文本串为 T T T，模式串为 P P P，且 n n n 为文本串长度， m m m 为模式串长度， i i i 为指向文本串的指针， j j j 为指向模式串的指针。

2. 思想

如上图所示，在使用蛮力算法进行字符串匹配时，当 T [ i ] ≠ P [ j ] T[i] ne P[j] T[i]​=P[j] 时，我们会进行回退，即令 i ← i − j + 1 , j ← 0 i leftarrow i-j+1, jleftarrow 0 i←i−j+1,j←0。

但事实上，此例中， T [ i − j , i ) = P [ 0 , j ) = “ 000000 ” T[i-j, i) = P[0, j) = “000000” T[i−j,i)=P[0,j)=“000000”。因此，如果按照蛮力算法进行回退，则在下一轮比对中，前 j − 1 j-1 j−1 次比对必然都会成功。故而，可直接令 i i i 保持不变，令 j ← j − 1 j leftarrow j-1 j←j−1，然后继续比对（相当于直接跳过了那 j − 1 j-1 j−1 次必定会成功的比对）。如此，下一轮只需 1 1 1 次比对，共减少 j − 1 j - 1 j−1 次！

更加一般地，当 T [ i ] ≠ P [ j ] T[i] ne P[j] T[i]​=P[j] 时，我们只回退指针 j j j，而保持指针 i i i 不变，即让 T [ i ] T[i] T[i] 与 P [ t ] P[t] P[t] 对齐，然后进行下一次比对。 上述 *** 作等价于将 P P P 右移 j − t j-t j−t 个单位。

问题是“如何确定 t t t”？

3. next表

根据前一轮比对可知，
P [ 0 , j ) = T [ i − j , i ) P[0, j) = T[i-j, i) P[0,j)=T[i−j,i)
且
P [ j ] ≠ T [ i ] P[j] ne T[i] P[j]​=T[i]

因此， t t t 需要满足，
P [ 0 , t ) = T [ i − t , i ) = P [ j − t , j ) P[0, t) = T[i-t, i) = P[j-t, j) P[0,t)=T[i−t,i)=P[j−t,j)

也就是说，在子串 P [ 0 , j ) P[0,j) P[0,j) 中，长度为 t t t 的真前缀应与长度为 t t t 的真后缀完全匹配。故， t t t 来自于集合，

N ( P , j ) = { 0 ≤ t < j ∣ P [ 0 , t ) = P [ j − t , j )   且   P [ t ] ≠ P [ j ] } N(P, j) = { 0 le t lt j | P[0, t) = P[j-t, j) 且 P[t] ne P[j] } N(P,j)={0≤t

因为回退指针 j j j 等价于将 P P P 右移 j − t j-t j−t 个单位，为了不遗漏任何可能的匹配，应该使用 j − t j-t j−t 尽可能地小，即让 t t t 尽可能地大。所以，

next [ j ] = t = max ⁡ ( N ( P , j ) ) text{next}[j] = t = max(N(P, j)) next[j]=t=max(N(P,j))

next [ j ] text{next}[j] next[j] 表示应该将指针 j j j 回退至哪个位置，也就是 t t t 的位置，使得 P [ 0 , t ) = P [ j − t , j ) P[0, t) = P[j-t, j) P[0,t)=P[j−t,j)。

另一个问题是，当 j = 0 j = 0 j=0 时， t t t 如何取值？

因为 t t t 满足，

N ( P , j ) = { 0 ≤ t < j ∣ P [ 0 , t ) = P [ j − t , j )   且   P [ t ] ≠ P [ j ] } N(P, j) = { 0 le t lt j | P[0, t) = P[j-t, j) 且 P[t] ne P[j] } N(P,j)={0≤t

当 j = 0 j=0 j=0 时，集合 N ( P , j ) N(P, j) N(P,j) 为空！对应的情况是： T [ i ] ≠ P [ 0 ] T[i] ne P[0] T[i]​=P[0]，即文本串与模式串的第一个字符不匹配。此时应当将 T T T 和 P P P 各自右移一个单位，即令 i ← i + 1 ileftarrow i+1 i←i+1，而令 j j j 保持为 0 0 0 不变。

上述情况等价于， next [ 0 ] = − 1 text{next}[0]=-1 next[0]=−1，然后在下一轮对比中， T [ i ] = P [ − 1 ] T[i] = P[-1] T[i]=P[−1]，接着各自前进一步，即令 i ← i + 1 , j ← j + 1 = 0 ileftarrow i+1, jleftarrow j+1 = 0 i←i+1,j←j+1=0。因此可以假设哨兵 P [ − 1 ] P[-1] P[−1] 是一个通配符。

接下来的问题是，如何构造 next 表？

令 t = next [ j ] t=text{next}[j] t=next[j]，它表示在子串 P [ 0 , j ) P[0,j) P[0,j) 中存在 P [ 0 , t ) = P [ j − t , j ) P[0,t) = P[j-t,j) P[0,t)=P[j−t,j)。因此存在 next [ j + 1 ] ≤ next [ j ] + 1 text{next}[j+1] le text{next}[j]+1 next[j+1]≤next[j]+1，当且仅当 P [ j ] = P [ t ] P[j] = P[t] P[j]=P[t] 时，等号成立。

根据 next 表的定义不难得知，当 P [ j ] ≠ P [ t ] P[j] ne P[t] P[j]​=P[t] 时， next [ j + 1 ] text{next}[j+1] next[j+1] 的下一个候选者依次为，

next [ next [ j ] ] + 1 , next [ next [ next [ j ] ] ] + 1 , . . . text{next}[text{next}[j]]+1, text{next}[text{next}[text{next}[j]]]+1, ... next[next[j]]+1,next[next[next[j]]]+1,...

不难发现，上述求解 next [ j + 1 ] text{next}[j+1] next[j+1] 的过程与 KMP 算法中文本串与模式串的匹配过程类似。KMP 算法尝试回退指针 j j j，使得 j ← t j leftarrow t j←t，以满足 P [ 0 , t ) = T [ i − t , i ) P[0, t) = T[i-t, i) P[0,t)=T[i−t,i)。而此处求解 next [ j + 1 ] text{next}[j+1] next[j+1] 的过程则是回退指针 t t t（此处的 t t t 相当于 KMP 算法中指向模式串的指针 j j j，而此处的 j + 1 j+1 j+1 则相当于 KMP 算法中指向文本串的指针 i i i），使得 t ← t ′ t leftarrow t' t←t′，以满足 P [ 0 , t ′ ) = P [ j + 1 − t ′ , j + 1 ) P[0, t') = P[j+1-t', j+1) P[0,t′)=P[j+1−t′,j+1)。

此外，还需要注意的一点是， N ( P , j ) N(P, j) N(P,j) 中还要求 P [ t ] ≠ P [ j ] P[t] ne P[j] P[t]​=P[j]，对于此处来说就是要求 P [ t ′ ] ≠ P [ j + 1 ] P[t'] ne P[j+1] P[t′]​=P[j+1]。因为 T [ i ] ≠ P [ j + 1 ] T[i] ne P[j+1] T[i]​=P[j+1]，所以如果 next [ j + 1 ] = t ′ text{next}[j+1]=t' next[j+1]=t′ 且 P [ t ′ ] = P [ j + 1 ] P[t'] = P[j+1] P[t′]=P[j+1]，则下一次匹配依然会失败！优化的方法是，当 P [ t ′ ] = P [ j + 1 ] P[t'] = P[j+1] P[t′]=P[j+1] 时，令 next [ j + 1 ] = next [ t ′ ] text{next}[j+1] = text{next}[t'] next[j+1]=next[t′]。

4. 实现

int* buildNextTable(const string& pattern) {
    int m = pattern.size();
    int t = -1, j = 0;
    int* nextTable = new int[m];
    nextTable[0] = -1;
    m--;

    while (j < m) {
        if (t < 0 || pattern[j] == pattern[t]) {
            j++; t++;
            // nextTable[j] = t;    // 未优化
            nextTable[j] = (pattern[j] != pattern[t] ? t : nextTable[t]);
        } else {
            t = nextTable[t];
        }
    }

    return nextTable;
}

int kmpMatch(const string& text, const string& pattern) {
    int* nextTable = buildNextTable(pattern);
    int n = text.size(), m = pattern.size();
    int i = 0, j = 0;

    while (i < n && j < m) {
        if (j < 0 || text[i] == pattern[j]) {
            i++; j++;
        } else {
            j = nextTable[j];
        }
    }

    delete []nextTable;
    return i-j;
}