字符串匹配简单算法（ bm, kmp, 哈希）算法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秒内完成。

哈希求解 (RK, Rabin-Carp) 暴力求解里面，内层循环用来匹配每个位置对应的子串是否和模式串匹配。这个比较过程
是可以优化的。
我们将 a-z 这26个字符映射到 0-25，将字符串当作 26 进制整数进行匹配，就可以高效地
进行模式串 P 的匹配，从而将内层循环去掉。算法复杂度是 \( O(n) \)
这个算法的缺点是整数可能溢出。解决办法是使用其它哈希方法，例如将字符串哈希为每个
字符的和，但这会造成哈希值冲突，为了解决冲突，需要在哈希值匹配之后，对字符串逐一
比较。如果存在大量哈希冲突，每次都要再对比字串，因此这样的方法最差时间复杂度是
\( O(nm) \) 。实际上除非模式串较大，否则遇到哈希冲突的情况是非常少的。收到
Bloom-filter 算法的启发，我曾同时使用 8 个不同的哈希函数计算匹配哈希值，模式串不
长所以基本不会冲突，速度很快。缺点就是总被人问“你搞的什么鬼”。后来有人改成了KMP
算法，业务上线2年后发现写错了，review 名单里面也有我，尴尬的很。写错的算法
还不如暴力求解。

BM 算法 (Boyer-Moore) 让我们仔细查看 \( 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字节吗？
这种情况可以观察下图，蓝色部分为模式串中前缀等于后缀的部分。由于好已经匹配的好后
缀在模式串中没有其它对应，退而求其次，右移模式串，直到前缀与后缀相等的位置。

文章图片

如果模式串中间也出现一个蓝色部分，与其中蓝色的前缀、后缀相等，这时不需要考虑的。因
为即使移动中间蓝色部分到后缀蓝色部分相等，由于匹配的好后缀前提已经没有在模式串中
有其它对应了，即使将蓝色子串对应，最终也找不到好后缀从而再次右移。
【字符串匹配简单算法（ bm, kmp, 哈希）】
BM 算法实现坏字符规则很容易实现，只要构建一个表，可以查找某个字符在模式串中最后出现的位置即
可。
问题是好后缀规则如何高效实现。
我们引入 \( 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 generate_bad_char(string P) { vector 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&suffix, vector&prefix) { suffix = vector(P.size()); prefix = vector(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, vectorsuffix, vectorprefix) { 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 suffix; vector 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 算法的复杂度 BM 的算法复杂度分析很难，Tight Bounds On The Complexity Of The Boyer-Moore
String Maching Algorithm 证明 BM 算法的比较次数上限是 \( 3n \) 。

KMP 算法 (Knuth Morris Pratt) 我从来没有在实际工作中实现过 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 gen_next(string P) { vector 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) \) 。