字符串匹配算法: kmp和bm算法

字符串匹配，是开发工作中最常见的问题之一。它要求从一个较长的字符串中查找一个较短的字符串的位置。例如从字符串 \(T=bacbababaabcbab\) 中查找字符串 \(P=ababaca\) 的位置。 \(T\) 称为*主串*， 字符串 \(P\) 称为*模式串*。

这个问题历史悠久而且经常出现，因此有很多解决这个问题的算法。

通常最容易想到的是朴素匹配算法，也叫暴力求解。简单地说，就是对 \(T\) 中所有可能位置逐一与 \(P\) 匹配。 例如 \(T=badcab\) ， \(P=dca\) ：

badcab
dca    -- 比较 dca 与 bad, 不匹配
 dca   -- 比较 dca 与 adc, 不匹配
  dca  -- 比较 dca 与 dca，匹配，返回当前位置 2

匹配代码如下：

int search(const string &T, const string&P) {
    if (P.empty()) { // 模式串为空，匹配任意字符串
        return 0;
    }
    // i<=T.size()-P.size() 是为了 T[i+j] 不越界
    for (size_t i = 0; i <= T.size() - P.size(); ++i) {
        for (size_t j = 0; j < P.size(); ++j) {
            if (T[i + j] != P[j]) {
                break;
            }
            if (j == P.size() - 1) {
                return i;
            }
        }
    }
    return -1; // -1 表示没有匹配
}

设 \(n=T.size()\) ， \(m=P.size()\) ， 显然这个算法的复杂度是 \(O(nm)\) 。

这个算法简单，有效，不容易出错。大部分情况下，暴力求解够用了。在我的 PC 上，算法复杂度带入参数后， 计算 \(1e7\) 以下的算法， 基本可以在1秒内完成。

暴力求解里面，内层循环用来匹配每个位置对应的子串是否和模式串匹配。 这个比较过程是可以优化的。

我们将 a-z 这26个字符映射到 0-25，将字符串当作 26 进制整数进行匹配，就可以高效地进行模式串 P 的匹配，从而将内层循环去掉。 算法复杂度是 \(O(n)\)

这个算法的缺点是整数可能溢出。解决办法是使用其它哈希方法，例如将字符串哈希为每个字符的和，但这会造成哈希值冲突，为了解决冲突，需要在哈希值匹配之后，对字符串逐一比较。如果存在大量哈希冲突，每次都要再对比字串，因此这样的方法最差时间复杂度是 \(O(nm)\) 。实际上除非模式串较大，否则遇到哈希冲突的情况是非常少的。受到 Bloom-filter 算法的启发，我曾同时使用 8 个不同的哈希函数计算匹配哈希值，模式串不长所以基本不会冲突，速度很快。缺点就是总被人问“你搞的什么鬼”。后来有人改成了KMP 算法，业务上线2年后发现写错了，review 名单里面也有我， 尴尬的很。写错的算法还不如暴力求解。

让我们仔细查看 \(T=abcacabdc\) ， \(P=abd\) 情况，尝试使用暴力求解方法对其匹配。

   abcacabdc
1: abd| | |  -- 不匹配
2:  abd | |  -- 不匹配
3:   abd| |  ..
4:    abd |  ..
5:     abd|  -- 不匹配
6:      abd  -- 匹配!

第1轮匹配时，主串出现字符 \(c\) ， \(c\) 并没有在模式串中出现，其实可以直接将模式串整体后移到主串的 \(c\) 之后。

第2轮匹配时，模式串 \(d\) 对应对应主串的 \(a\) ，不匹配，右移1字节。如果知道 \(a\) 在模式串中最后出现的位置是 0, 那么直接后移2字节，让主串的 \(a\) 直接与模式串的 \(a\) 对正，可以节省很多时间。

我从来没有在实际工作中实现过 KMP 算法，倒是有不少人，正好最近看了 KMP 或者红黑树之后就到面试官职位上显摆，让人手写一个，最近正好看过倒也不难。 虽然平时没什么用，但算法对人思维的启发性也是有意义的，因为与其类似的 AC 自动机算法经常要自己实现。

KMP 算法的思想与 BM 算法类似。它顺序比较模式串，如果遇到坏字符，就向右移动直到前缀匹配到好前缀。 观察下面的例子。

     v
ababaeabac
ababacd
---
 \ \
  ---
  ababacd

匹配到坏字符 \(e\) 时， \(P\) 的好前缀 \(ababa\) 已经确定匹配了。我们发现：

ababa
  ababa

这个好前缀的前缀与后缀有一个最长的匹配，我们右移 \(P\) 时，可以直接移动到令这个最长匹配对应。它是最长匹配，移动位数小于它的总是比它差，直接移动到令最长匹配对正就可以。

实现需要一个 \(next\) 数组，\(next[i]\) 表示 \(P[0..i]\) 的后缀中最长可匹配前缀子串的下标。 例如字符串 \(P=ababacd\) :

计算 \(next\) 数组使用的是类似动态规划的方法。

• \(next[i]=k\) 等价于 \(P[0..k]=P[i-k..i]\) 。此时若 \(P[k+1]=P[i+1]\) , 那么 \(P[0..k+1]=P[i-k..i+1]\) , 即 \(next[i+1]=k+1\) 。
• 若 \(P[k+1]\neq P[i+1]\) ，就要尝试更短长度的前缀后缀匹配。令 \(m=next[k]\) ， \(P[0..m]=P[i-m..i]\) 。若 \(P[m+1]=P[i+1]\) ，那么 \(next[i+1]=m+1\) 。以此类推。

实现如下：

vector<int> gen_next(string P) {
    vector<int> next(P.size());
    if (P.empty()) {
        return next;
    }

    next[0] = -1;
    int k = -1;
    for (int i = 1; i < P.size(); ++i) {
        while (k != -1 && P[k+1] != P[i]) {
            k = next[k];
        }
        if (P[k+1] == P[i]) {
            ++k;
        }
        next[i] = k;
    }
    return next;
}

int kmp(string T, string P) {
    if (P.empty()) { // 模式串为空，匹配任意字符串
        return 0;
    }
    if (P.size() > T.size()) { // 模式串比主串还大，肯定不匹配
        return -1; // 不匹配返回 -1
    }

    auto next = gen_next(P);
    int j = 0;
    for (int i = 0; i < T.size(); ++i) {
        while (j > 0 && T[i] != P[j]) {
            j = next[j - 1] + 1;
        }
        if (T[i] == P[j]) {
            ++j;
        }
        if (j == P.size()) {
            return i - P.size() + 1;
        }
    }
    return -1;
}

KMP 算法的复杂度不难计算。 \(next\) 数组构建时， while 循环分析有点麻烦。可以这么想： 每次循环，\(k\) 要么增加1，要么减少。增加的地方只有 \(++k\) ， 在 for 循环中，所以最多执行 \(m-1\) 次。 \(k\) 减少是在 while 循环中，因为它最小值 \(-1\) 后不可能再递减，所以最多执行 \(m-1\) 次。 因此计算 \(next\) 数组的时间复杂度是 \(O(m)\) 。

同理，匹配 \(T\) 时复杂度是 \(O(n)\) 。 KMP 的总体时间复杂度是 \(O(n+m)\) 。