子字符串匹配

子字符串匹配算法的定义：

• 文本长度：N
• 模式字符串长度：M
• 有效位移：s

解决字符串匹配的算法有非常多，目前常用的有以下几种：

• 暴力查找
• KMP 算法
• Boyer-Moore算法
• Rabin-Karp指纹字符串查找

字符串匹配算法通常分为两个步骤：预处理（Preprocessing）和匹配（Matching）。所以算法的总运行时间为预处理和匹配的时间的总和。

常用算法

暴力查找

朴素的字符串匹配算法又称为暴力匹配算法（Brute Force Algorithm），它的主要特点是：

• 没有预处理阶段；
• 滑动窗口总是后移 1 位；
• 对模式中的字符的比较顺序不限定，可以从前到后，也可以从后到前；
• 匹配阶段需要 O((n - m + 1)m) 的时间复杂度；
• 需要 2n 次的字符比较；

KMP 算法

详细过程：

从左到右匹配，直到匹配到第一个字符相等，如下图所示，然后继续匹配后面的字符。

到了D，发现不对，这是如果暴力法，则直接将模式后移一位，重新匹配。KMP算法的想法是，设法利用这个已知信息，不要把"搜索位置"移回已经比较过的位置，继续把它向后移，这样就提高了效率。

在查找的一开始根据模式字符串，生成一张《部分匹配表》（Partial Match Table）

移动位数 = 已匹配的字符数 - 对应的部分匹配值

所以移动为数 = 6 - 2 =4

这个《部分匹配表》如何生成？

"部分匹配值"就是"前缀"和"后缀"的最长的共有元素的长度。以"ABCDABD"为例，

－　"A"的前缀和后缀都为空集，共有元素的长度为0；
－　"AB"的前缀为[A]，后缀为[B]，共有元素的长度为0；
－　"ABC"的前缀为[A, AB]，后缀为[BC, C]，共有元素的长度0；
－　"ABCD"的前缀为[A, AB, ABC]，后缀为[BCD, CD, D]，共有元素的长度为0；
－　"ABCDA"的前缀为[A, AB, ABC, ABCD]，后缀为[BCDA, CDA, DA, A]，共有元素为"A"，长度为1；
－　"ABCDAB"的前缀为[A, AB, ABC, ABCD, ABCDA]，后缀为[BCDAB, CDAB, DAB, AB, B]，共有元素为"AB"，长度为2；
－　"ABCDABD"的前缀为[A, AB, ABC, ABCD, ABCDA, ABCDAB]，后缀为[BCDABD, CDABD, DABD, ABD, BD, D]，共有元素的长度为0。
复制代码

Boyer-Moore

几种常见的字符串匹配算法的性能比较：

KMP算法并不是效率最高的算法，实际采用并不多。各种文本编辑器的"查找"功能（Ctrl+F），大多采用Boyer-Moore算法。

详细过程：

首先，"字符串"与"搜索词"头部对齐，从尾部开始比较。我们看到，"S"与"E"不匹配。这时，"S"就被称为"坏字符"（bad character），即不匹配的字符。我们还发现，"S"不包含在搜索词"EXAMPLE"之中，这意味着可以把搜索词直接移到"S"的后一位。

依然从尾部开始比较，发现"P"与"E"不匹配，所以"P"是"坏字符"。但是，"P"包含在搜索词"EXAMPLE"之中。所以，将搜索词后移两位，两个"P"对齐。

"坏字符规则"：后移位数 = 坏字符的位置 - 搜索词中的上一次出现位置（如果"坏字符"不包含在搜索词之中，则上一次出现位置为 -1）

上图中，比较的是P和E，出现在第6位（0开始），然后P上一次位置是4，所以6-4=2

接着继续，一直比较到M：

根据"坏字符规则"，此时搜索词应该后移 2 - （-1）= 3 位。问题是，此时有没有更好的移法？

比较前面一位，"MPLE"与"MPLE"匹配。我们把这种情况称为"好后缀"（good suffix），即所有尾部匹配的字符串。注意，"MPLE"、"PLE"、"LE"、"E"都是好后缀

"好后缀规则"：后移位数 = 好后缀的位置 - 搜索词中的上一次出现位置

这个规则有三个注意点：

（1）"好后缀"的位置以最后一个字符为准。假定"ABCDEF"的"EF"是好后缀，则它的位置以"F"为准，即5（从0开始计算）。

（2）如果"好后缀"在搜索词中只出现一次，则它的上一次出现位置为 -1。比如，"EF"在"ABCDEF"之中只出现一次，则它的上一次出现位置为-1（即未出现）。

（3）如果"好后缀"有多个，则除了最长的那个"好后缀"，其他"好后缀"的上一次出现位置必须在头部。比如，假定"BABCDAB"的"好后缀"是"DAB"、"AB"、"B"，请问这时"好后缀"的上一次出现位置是什么？回答是，此时采用的好后缀是"B"，它的上一次出现位置是头部，即第0位。这个规则也可以这样表达：如果最长的那个"好后缀"只出现一次，则可以把搜索词改写成如下形式进行位置计算"(DA)BABCDAB"，即虚拟加入最前面的"DA"。

回到上文的这个例子。此时，所有的"好后缀"（MPLE、PLE、LE、E）之中，只有"E"在"EXAMPLE"还出现在头部，所以后移 6 - 0 = 6位。

可以看到，"坏字符规则"只能移3位，"好后缀规则"可以移6位。所以，Boyer-Moore算法的基本思想是，每次后移这两个规则之中的较大值。

Boyer–Moore 算法的精妙之处在于，其通过两种启示规则来计算后移位数，且其计算过程只与模式 P 有关，而与文本 T 无关。因此，在对模式 P 进行预处理时，可预先生成 "坏字符规则之向后位移表" 和 "好后缀规则之向后位移表"，在具体匹配时仅需查表比较两者中最大的位移即可。

Rabin-Karp

首先计算模式字符串的散列函数, 如果找到一个和模式字符串散列值相同的子字符串, 那么继续验证两者是否匹配.

这个过程等价于将模式保存在一个散列表中, 然后在文本中的所有子字符串查找. 但不需要为散列表预留任何空间, 因为它只有一个元素.

基本思想

长度为M的字符串对应着一个R进制的M位数, 为了用一张大小为Q的散列表来保存这种类型的键, 需要一个能够将R进制的M位数转化为一个0到Q-1之间的int值散列函数, 这里可以用除留取余法.

举个例子, 需要在文本 3 1 4 1 5 9 2 6 5 3 5 8 9 7 9 3 查找模式 2 6 5 3 5， 这里R=10， 取Q=997, 则散列值为

2 6 5 3 6 % 997 = 613
复制代码

然后计算文本中所有长度为5的子字符串并寻找匹配

3 1 4 1 5 % 997 = 508
1 4 1 5 9 % 997 = 201
......
2 6 5 3 6 % 997 = 613 (匹配)
复制代码

计算散列函数

在实际中，对于5位的数值, 只需要使用int就可以完成所有需要的计算, 但是当模式长度太大时, 我们使用Horner方法计算模式字符串的散列值

2 % 997 = 2

2 6 % 997 = (2*10 + 6) % 997 = 26

2 6 5 % 997 = (26*10 + 5) % 997 = 265

2 6 5 3 % 997 = (265*10 + 3) % 997 = 659

2 6 5 3 5 % 997 = (659*10 + 5) % 997 = 613

这里关键的一点就是在于不需要保存这些数的值, 只需保存它们除以Q之后的余数.

取余操作的一个基本性质是如果每次算术操作之后都将结果除以Q并取余, 这等价于在完成所有算术操作之后再将最后的结果除以Q并取余.

算法实现：

构造函数为模式字符串计算了散列值patHash并在变量中保存了R^(M-1) mod Q的值, hashSearch()计算了文本前M个字母的散列值并和模式字符串的散列值比较, 如果没有匹配, 文本指针继续下移一位, 计算新的散列值再次比较,知道成功或结束.

蒙特卡洛算法和拉斯维加斯算法区别：

总结

优点：

• 暴力查找算法：实现简单且在一般情况下工作良好（Java的String类型的indexOf()方法就是采用暴力子字符串查找算法）；
• Knuth-Morris-Pratt算法能够保证线性级别的性能且不需要在正文中回退；
• Boyer-Moore算法的性能一般情况下都是亚线性级别；
• Rabin-Karp算法是线性级别；

缺点：

• 暴力查找算法所需时间可能和NM成正比；
• Knuth-Morris-Pratt算法和Boyer-Moore算法需要额外的内存空间；
• Rabin-Karp算法内循环很长（若干次算术运算，其他算法都只需要比较字符）；