数据结构与算法之美 | 字符串匹配算法原理详解（哈希、KMP、BM、星期日）

0.引言

字符串的定位操作通常称作字符串的模式匹配，是各种字符串处理系统中最重要的操作之一，本文介绍Hash、KMP、BM、Sunday四种匹配算法。

1. 字符串Hash

字符串Hash就是在字符串上进行哈希，可通俗理解为把字符串转为整数，最后构建理想状态下的一个整数对应一个字符串的单射。

给定一个字符串S，我们规定:

1.1 自然溢出法

自然溢出Hash公式为:

这里的hash数组利用了unsigned long long的自然溢出对(2^{64} - 1)(264−1)取模。

1.2 单Hash法

单hash公式为:

其中p和mod均为素数，且p<mod，为了降低hash冲突，可让p和mod尽量往大取。

当一个哈希值对应两个或多个字符串时出现哈希冲突

取素数可以有效避免冲突，可以参照以下例子：

设函数表达式为f(y, x) = y∗x mod N

当N = 8，y = 2时：

当N = 7，y = 2时：

可以看出取素数冲突变少了。

1.3 双Hash法

将一个字符串用不同的mod hash两次，再将两个结果用一个二元组表示，构成一个

1.4 字符串hash的获取

根据定义可以得出:

/

hash[1]=s_1hash[1]=s1
hash[2]=s_1\times p+s_2hash[2]=s1×p+s2
hash[3]=s_1\times p^2+s_2\times p+s_3hash[3]=s1×p2+s2×p+s3
hash[4]=s_1\times p^3+s_2\times p^2+s_3\times p+s_4hash[4]=s1×p3+s2×p2+s3×p+s4

又由

hash[3,4]=s_3\times p+s_4hash[3,4]=s3​×p+s4​
hash[4]=s_1\times p^3+s_2\times p^2+s_3\times p+s_4hash[4]=s1​×p3+s2​×p2+s3​×p+s4​
hash[2]=s_1\times p+s_2hash[2]=s1​×p+s2​

可以得出:

所以得出通式为:

又因为每次都要取模，并且做减法时有可能出现负数，所以对其加mod后再取余做出修正，得到求字符串hash的最终公式为:

2. KMP

字符串查找算法(Knuth-Morris-Pratt )，简称为KMP算法，常用于在一个文本串S内查找一个模式串P 的出现位置，时间复杂度为O(n+m)，其中n为文本串的长度，m为模式串的长度。

KMP算法需要先寻找模式串中最长相等的前缀和后缀lps。

假设模式串P为: “bcdebcd”

可找到的前缀prefix有: “b”、“bc”、“bcd”、“bcde”

可找到的后缀suffix有: “d”、“cd”、“bcd”、“ebcd”

可得出lps为: “bcd”

因此可以根据模式串的lps来建立dp数组储存字符串再次出现的位置:

设文本串S为"bcbcdbcdbcbcbce"，模式串P为"bcbce"，模式串的dp数组为[0,0,1,2,0],匹配过程如下:

step1:

此时S串的i位字符与P串的j+1位字符匹配，i和j分别前进一位。

step2:

依次进行匹配…

step5:

此时S串的i位字符为"d"，P串的j+1位字符为"e"，匹配失败，根据dp数组，字符"c"在P串的2号位出现过，j要从4号位回退到2号位，所以P串向右移动2位，i不变。

step6:

此时S串的i位字符"d"与P串的j+1位字符"b"失配，因为dp数组中字符"c"在之前没有出现过，则j要回退到0号位，所以P串向右移动2位，i不变。

step7:

接上一步，S串的i位字符与P串的j+1位字符失配，因为j已经回退到了0号位，不能再回退，所以让i前进一位。

step8:

再依次进行匹配

step9:

step10:

此时S串的i位字符为"d"，P串的j+1位字符为"b"，匹配失败，根据dp数组要让j回退到0号位，所以模式串向右移动2位，i不变。

step11:

根据规则再依次进行匹配

step12:

…

step19:

此时S串的i位字符为最后一个字符"e"，P串的j位于的4号位，i位字符与j+1位字符匹配，则i和j分别再前进一位。

step20:

此时i已超出S串的边界，j位于P串的5号位，且等于P串的长度，则整个字符串匹配成功。

如果我们把匹配转移和失配转移用有限状态自动机(FSM)的形式来表示，根据模式串bcbce的dp数组[0,0,1,2,0]可以得出下面一个状态转移图:

注意: 这里进行文本串遍历的i与BF算法(即暴力(Brute Force)算法)进行文本串遍历的i不同，BF算法进行文本串遍历的i是指起始位置，KMP算法进行文本串遍历的i是指当前匹配到的位置。

3. BM

BM(Boyer-Moore)算法则与KMP算法不同，KMP算法的模式串是从前往后遍历，BM算法的模式串是从后往前遍历。BM算法的时间复杂度最好为O(n/m)，最坏为O(nm)，其中n为文本串的长度，m为模式串的长度。BM算法有两条规则，分别是坏字符串规则(Bad character rule)和好前缀规则(Good suffix rule)，根据这两条规则相互竞争来进行字符串匹配。

3.1 坏字符串规则