KMP Algorithm

7 minute
3030 words
Tags:
#Algorithm

KMP 算法

思想

KMP 算法, 全程 Knuth-Morris-Pratt 算法, 是一种高效的字符串匹配算法. 它的核心思想是:
在匹配过程中, 当发生文本串(text)与模式串(pattern)不匹配时, 能够利用已匹配过的部分信息, 智能地移动模式串, 从而避免从头开始匹配, 达到提高匹配效率的目的.

KMP算法的巧妙之处在于:
它认为, 当发生不匹配时, 将模式串仅仅右移一位是"愚蠢"的. 当某个地方不匹配时, 表明前面实际上有部分内容已经匹配了. 如果直接从头开始匹配, 就浪费了这些信息. 有时前面已经匹配部分会有"重复"的性质, 可以利用这种性质, 让子串一次多移动几步, 从而加速匹配速度.

举例 主串S和模式串P

PLAINTEXT
S = BBC ABCDAB ABCDABCDABDE
P = ABCDABD
Click to expand and view more

当匹配到下面这种情况时:

PLAINTEXT
S = BBC ABCDAB ABCDABCDABDE  
P =     ABCDABD
Click to expand and view more

这里的 D 和上面空格不匹配, 此时保理匹配就直接向右移动一位, 但是通过观察已经匹配的部分 “ABCDAB” 可以发现, 该部分有相同的前后缀 “AB”, 因此可以直接将子串的 “A” 对准主串中后缀 “AB” 里面的 “A”:

PLAINTEXT
S = BBC ABCDAB ABCDABCDABDE
P =         ABCDABD
Click to expand and view more

此时, S 的指针不用改变, 将 P 的指针回到 “C” 的位置就行了. 通过这种方法, 大大提升了效率.

这里的思想就是: 如果已匹配部分有相同的最大前后缀, 那么当发生不匹配时, 可以直接将已匹配部分的, 模式串的前缀对准主串的后缀, 对应 j = next[j](或者有的地方是 j = next[j - 1]), 就可以一次多移动几步, 而不是朴素算法的一步.

此外, KMP 不仅是利用了 “最大相同前后缀” 来移动多步模式串的思想, 即使在模式串没有任何 “最大相同前后缀” 的时候, 其时间复杂度仍然为 O(m + n)
看下面这个例子:

PLAINTEXT
文本: X Y C D E F G
模式: X Y Z
Click to expand and view more

这里 Z 和 C 不匹配, 朴素算法会将 i 回溯到 Y, j 回溯到 X:

PLAINTEXT
文本: X Y C D E F G
模式:   X Y Z
Click to expand and view more

而 KMP 算法此时的 next = [0, 0, 0], 因此将 j 回溯到 X (j=0), 而 i 不变, 因为它知道前面已匹配的部分中, 没有任何可以利用的前后缀信息, 因此可以一次移动很多步

PLAINTEXT
文本: X Y C D E F G
模式:     X Y Z
Click to expand and view more

再来看一个已匹配部分的前缀有公共前后缀的例子:

PLAINTEXT
文本: A B A C B ...
模式: A B A C D
Click to expand and view more

这里发现 D 不匹配, 已匹配部分为 “ABAC”, 其没有任何公共前后缀, 虽然 “ABA” 有公共前后缀 “A”, 但是这个信息在这里并没有用, 因为我们知道"AB" 和 “AC” 是不匹配的, 因此不用移动成这样:

PLAINTEXT
文本: A B A C B ...
模式:     A B A C D
Click to expand and view more

而是直接移动成这样

PLAINTEXT
文本: A B A C B ...
模式:         A B A C D
Click to expand and view more

所以, KMP 的思想不仅仅是利用了 “最大公共前后缀” 来加速匹配速度, 同时也利用了, 当没有 “公共前后缀” 的情况加速匹配速度的思想. 在 KMP 中, 主串的指针 i 是永不回溯的, 要回溯的只有模式串的指针 j.

实现

PM (Partial Match) 表
PM 表是"部分匹配表", 用于构造 next 数组, 对于子串 P = "ABCDABD" 为例, 计算其 PM 表:

故得到模式串 P = "ABCDABD" 的 PM 表为 [0, 0, 0, 0, 1, 2, 0]

next 数组
next 数组就是在代码中实际使用的数组, 一般有两种方法, 当 P[j] 匹配失败的时候, 会使用 j = next[j] 或者 j = next[j - 1] 的方法来进行回溯, 下面介绍第一种:
0. PM 表为 [0, 0, 0, 0, 1, 2, 0]

  1. 将 PM 表向右移动一位: [_, 0, 0, 0, 0, 1, 2]
  2. 在开头补上 -1: [-1, 0, 0, 0, 0, 1, 2]
CPP
void getNext_standard(string& P, vector<int>& next) {
    int m = P.length();
    next.resize(m);

    next[0] = 0; // 单个字符没有前后缀

    int j = 0; // j 记录最长前后缀的长度

    // i 从 1 开始遍历模式串
    for (int i = 1; i < m; ++i) {
        // 如果当前字符不匹配, j 回溯
        // j > 0 防止越界
        while (j > 0 && P[i] != P[j]) {
            // j 回溯到上一个子串最长相同前后缀的长度
            j = next[j - 1];
        }

        // 如果匹配, j + 1
        if (P[i] == P[j]) {
            ++j;
        }
    }
}
Click to expand and view more
CPP
void getNext_sentinel(const std::string& P, std::vector<int>& next) {
    int m = P.length();
    next.resize(m);

    // next[0] 设置为 -1 作为哨兵
    next[0] = -1;
    
    // i 遍历模式串，j 记录最长相等前后缀长度
    // 注意这里 j 的初始值是 -1，与 next[0] 对应
    int i = 0, j = -1;
    
    // 循环直到遍历完模式串
    while (i < m - 1) {
        // 当 j 为 -1 或当前字符匹配时，i 和 j 同时向后移动
        if (j == -1 || P[i] == P[j]) {
            i++;
            j++;
            // 更新 next[i]
            next[i] = j;
        } else {
            // 当字符不匹配时，j 回溯到 next[j]
            j = next[j];
        }
    }
}
Click to expand and view more

nextval 数组
next 数组已经很高效了, 但还可以进一步优化为 nextval 数组, 考虑一下情况:

PLAINTEXT
S: A A A B <- i
P: A A A A <- j
Click to expand and view more

这时 P[3] 和 S[3] 不匹配, 根据 P 的 next 数组 [-1, 0, 1, 2, 3] 可知下一次匹配应该是这样:

PLAINTEXT
S: A A A B
P:   A A A A
         ^
         j
Click to expand and view more

这时候发现, 之前的 P[3] 和现在 j 回退后指向的 P[2] 都是 “A”, 因此肯定不匹配, 故应该继续回退.
这里就是 nextval 数组的优化, 也是唯一和 next 数组不同的地方:
当 P[j] == P[next[j]] 的时候, 这回退是没有意义的, 因此要继续回退, 直到 P[k] 和 P[j] 不同的位置 k

PLAINTEXT
// 基于 next 数组计算 nextval 数组
void getNextval(const string& P, vector<int>& nextval) {
    int m = P.length();
    vector<int> next(m);
    getNext(P, next); // 首先计算 next 数组

    nextval.resize(m);
    nextval[0] = 0; // nextval[0] 同样为 0

    for (int i = 1; i < m; ++i) {
        // 如果 P[i] 等于 P[next[i] - 1]，说明当前最长相等前后缀的下一个字符与当前字符相同
        if (next[i] > 0 && P[i] == P[next[i] - 1]) {
            // 回溯到 next[i] 的 nextval 值
            nextval[i] = nextval[next[i] - 1];
        } else {
            // 否则，nextval[i] 就等于 next[i]
            nextval[i] = next[i];
        }
    }
}
Click to expand and view more
CPP
void getNextval(const string& P, vector<int>& nextval) {
    int m = P.length();
    nextval.resize(m);

    // j 记录最长相等前后缀的长度
    int j = 0; 
    
    // nextval[0] 始终为 0
    nextval[0] = 0;
    
    // i 从 1 开始遍历模式串
    for (int i = 1; i < m; ++i) {
        // 如果当前字符不匹配，j 回溯
        while (j > 0 && P[i] != P[j]) {
            // 注意：这里利用 nextval 数组自身进行回溯
            j = nextval[j - 1]; 
        }

        // 如果字符匹配，j 增加 1
        if (P[i] == P[j]) {
            j++;
        }

        // 更新 nextval[i]
        // 关键逻辑: 如果 P[i] 和 P[j] 相等，那么 nextval[i] 的值等于 nextval[j]
        // 否则, nextval[i] 等于 j
        if (j > 0 && P[i] == P[j]) { // 与 next 区别点
            nextval[i] = nextval[j];
        } else {
            nextval[i] = j;
        }
    }
}
Click to expand and view more

KMP In Action

下面使用 c++ 代码来完成 KMP 算法

CPP
#include <iostream>
#include <vector>
#include <string>

using namespace std;

// KMP 算法中的 next 数组计算 (常规版本)
void getNext(const string& P, vector<int>& next) {
    int m = P.length();
    next.resize(m);
    int j = 0;
    next[0] = 0;
    for (int i = 1; i < m; ++i) {
        while (j > 0 && P[i] != P[j]) {
            j = next[j - 1];
        }
        if (P[i] == P[j]) {
            j++;
        }
        next[i] = j;
    }
}

// 完整的 KMP 匹配算法
int KMP_standard(const string& T, const string& P) {
    int n = T.length();
    int m = P.length();
    
    if (m == 0) return 0;

    // 计算 next 数组
    vector<int> next;
    getNext(P, next);

    int i = 0; // 主串指针
    int j = 0; // 模式串指针

    while (i < n) {
        // 如果字符匹配，两个指针同时后移
        if (T[i] == P[j]) {
            i++;
            j++;
        }
        
        // 匹配成功，返回起始位置
        if (j == m) {
            // j = next[j-1]; // 如果需要查找所有匹配，则继续
            return i - j;
        }

        // 匹配失败
        if (i < n && T[i] != P[j]) {
            // 如果 j > 0, 说明模式串可以回溯
            if (j > 0) {
                j = next[j - 1];
            } else {
                // 如果 j 已经是 0, 说明无法回溯, 主串指针后移
                i++;
            }
        }
    }

    return -1; // 匹配失败
}

int main() {
    string text = "ABABABABCABABABABD";
    string pattern = "ABABABD";

    cout << "主串: " << text << endl;
    cout << "模式串: " << pattern << endl;

    int pos = KMP_standard(text, pattern);
    if (pos != -1) {
        cout << "使用标准 next 数组, 匹配成功, 起始位置: " << pos << endl;
    } else {
        cout << "使用标准 next 数组, 匹配失败" << endl;
    }

    return 0;
}
Click to expand and view more

Start searching

Enter keywords to search articles

↑↓
↵
ESC
⌘K Shortcut