关于算法:字符串匹配简单算法-bm-kmp-哈希

字符串匹配，是开发工作中最常见的问题之一。它要求从一个较长的字符串中查找一个较短
的字符串的地位。例如从字符串 \(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;
    }
    if (P.size() > T.size()) { // 模式串比主串还大，必定不匹配
        return -1; // 不匹配返回 -1
    }
    for (size_t i = 0; i < T.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 \) 之后。

第 2 轮匹配时，模式串 \(d \) 对应对应主串的 \(a \)，不匹配，右移 1 字节。如果晓得 \(a \) 再
模式串中最初呈现的地位是 0, 那么间接后移 2 字节，让主串的 \(a \) 间接与模式串的 \(a \)
对正，能够节俭很多工夫。

暴力求解中，模式串与主串依照下标程序从小到大匹配，BM 算法反而从大到小匹配。从模
式串开端向前倒着匹配，当发现某个字符无奈匹配的时候，主串的这个字符就称为
“ 坏字符 ”。如上例中的第 1 轮匹配的 \(c \)，也如上例中第 4 轮匹配的最右侧 \(a \)。

上面这一轮匹配，坏字符 \(c \) 在模式串中不存在，能够间接将模式串挪动到 \(c \) 前面。

abcacabdc
abd
   abd

上面这一轮匹配，坏字符 \(a \) 在模式串中的地位为 0，能够间接将模式串右移 2 字节，
另模式串的 \(a \) 与主串的坏字符 \(a \) 对正。

abcacabdc
   abd
     abd

实际上，坏字符呈现时，咱们将模式串右移，直到模式串中最右侧呈现坏字符雷同的字符，
与主串的坏字符对正。

坏字符规定显然正确，只是，单纯应用坏字符规定还是不够的，
\(T=aaaaaaaaaaaaaaaaaaa \) , \(P=baaa \) 的状况下，应用坏字符规定时，跟暴力求解办法时一
样的。

好后缀规定与坏字符规定相似。咱们察看 \(T=abcacabcbcbacabc \) , \(P=abcabc \) 的匹配。

   v  __
abcacabcbcbacabc
 abbccbc
    abbccbc
      -- --

能够看到 “cabc” 匹配之后，呈现了坏字符 \(a \)，此时不思考坏字符规定，能够将模式串右
移 3 字节，令模式串中较前的 “bc” 挪动到以后地位后缀 “bc” 处。如果应用坏字符规定，
最初一个 \(a \) 的地位在左边，还要左移做无用功，只能进化到暴力求解办法。

咱们很容易事后了解模式串，理解其后缀与等于后缀的最长前缀地位，呈现了坏字
符时，间接将模式串右移，直到模式串中的前缀与曾经匹配的好后缀相等的地位。
如果字符串中有多个子串与后缀匹配，就抉择最左边的子串。

不难看出目前为止的好后缀规定与坏字符规定类似。

然而，当好后缀在模式串中找不到雷同的子串字母挪动？象暴力求解一样只右移 1 字节吗？
这种状况能够察看下图，蓝色局部为模式串中前缀等于后缀的局部。因为好曾经匹配的好后
缀在模式串中没有其它对应，退而求其次，右移模式串，直到前缀与后缀相等的地位。

如果模式串两头也呈现一个蓝色局部，与其中蓝色的前缀、后缀相等，这时不须要思考的。因
为即便挪动两头蓝色局部到后缀蓝色局部相等，因为匹配的好后缀前提曾经没有在模式串中
有其它对应了，即便将蓝色子串对应，最终也找不到好后缀从而再次右移。

坏字符规定很容易实现，只有构建一个表，能够查找某个字符在模式串中最初呈现的地位即
可。

问题是好后缀规定如何高效实现。

咱们引入 \(suffix \) 数组，\(suffix[i] \) 示意长度为 \(i \) 的后缀在模式串中相匹配的另一个
子串的地位。例如 \(P=cabcab \)：

后缀子串	长度(i)	suffix[i]	prefix[i]
b	1	2	false
ab	2	1	false
cab	3	0	true
bcab	4	-1	false
abcab	5	-1	false

\(suffix \) 数组能够解决好后缀在模式串中有其它匹配的子串的状况。当没有子串与好后缀
匹配时，还须要 \(prefix \) 数组。\(prefix[i] \) 示意长度为 \(i \) 的后缀与模式串前缀是否
相等。

实现代码如下：


// 字符集大小
const static int kMaxChar = 256; 
// 坏字符
vector<int> generate_bad_char(string P) {vector<int> bc(kMaxChar);
    fill(bc.begin(), bc.end(), -1); // 初始化
    for (int i = 0; i < P.size(); ++i) {bc[P[i]] = i;
    }
    return bc;
}

// 好后缀
void generate_good_suffix(string P, vector<int>&suffix, vector<bool>&prefix) {suffix = vector<int>(P.size());
    prefix = vector<bool>(P.size());
    fill(prefix.begin(), prefix.end(), false);
    fill(suffix.begin(), suffix.end(), -1);

    for (int i = 0; i < P.size() - 1; ++i) {// P[0..i] 中有没有后缀匹配
        int j = i;
        int k = 0; // 公共后缀子串的长度
        while (j >= 0 && P[j] == P[P.size() - 1 - k]) {// P[j..i] 与 P[...P.size()-1] 匹配
            --j; ++k;
            suffix[k] = j + 1;
        }
        if (j == -1) {// 后缀与前缀匹配 P[0..i] = P[...P.size()-1]
            prefix[k] = true;
        }
    }
}

// j 示意坏字符对应 P 的下标
// m 示意 P.size()
int move_gs(int j, int m, vector<int>suffix, vector<bool>prefix) {
    int k = m - 1 - j; // 好后缀长度
    if (suffix[k] != -1) { // P 中存在其余好后缀匹配
        return j - suffix[k] + 1;
    }
    for (int r = j + 2; r <= m - 1; ++r) {
        // 查找最长匹配的前缀
        if (prefix[m - r]) {return r;}
        return r;
    }
    // 都没匹配，就间接右移整串
    return m;
}

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

    auto bc = generate_bad_char(P);
    vector<int> suffix;
    vector<bool> prefix;
    generate_good_suffix(P, suffix, prefix);

    int i = 0; // 匹配地位
    while (i <= T.size() - P.size()) {
        int j;
        for (j = P.size()-1; j >= 0; --j) {// 模式串从后往前 P[j] .. P[0]
            if (T[i+j] != P[j]) {break; // 找到坏字符 T[i+j]
            }
        }
        if (j < 0) {return i; // 没有坏字符，匹配胜利}
        int x = j - bc[T[i+j]]; // 坏字符是 T[i+j]
        int y = 0;
        if (j < P.size() - 1) { // 存在好后缀
            y = move_gs(j, P.size(), suffix, prefix);
        }
        i = max(x, y);
    }
    return -1;
}

BM 的算法复杂度剖析很难，Tight Bounds On The Complexity Of The Boyer-Moore
String Maching Algorithm 证实 BM 算法的比拟次数下限是 \(3n \)。

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

KMP 算法的思维与 BM 算法相似。它程序比拟模式串，如果遇到坏字符，就向右挪动直到前
缀匹配到好前缀。察看上面的例子。

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

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

ababa
  ababa

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

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

P[0..i]	i	next[i]	阐明
a	0	-1	不存在
ab	1	-1	不存在
aba	2	0	P[0] = P[2]
abab	3	1	P[0..1] == P[2..3]
ababa	4	2	P[0..2] == P[2..4]
ababac	5	1	不存在

计算 \(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) \)。

关于算法:字符串匹配简单算法-bm-kmp-哈希

问题形容

暴力求解

哈希求解 (RK, Rabin-Carp)

BM 算法 (Boyer-Moore)

坏字符规定

好后缀规定

BM 算法实现

BM 算法的复杂度

KMP 算法 (Knuth Morris Pratt)