.NET源码学习 [算法2-数组与字符串的查找与匹配]( 九 ) _生活百科

文章插图
此外，若在模式串中若存在多个与好后缀匹配的相同字符串或与好后缀的后缀字串相同的模式串中的前缀子串，则选择最长且靠后的串并记为 { v }，按规则滑动。
以上就是BM算法的两个核心规则，在使用中可以分别计算好使用两用规则的滑动位数，取较大的一个 max( k1, k2 ) ，作为向后滑动的位数，这样既能使得时间复杂度接近最优的O( n / m ) ，也能避免滑动位数出现负数的情况。
具体实现如下：
（1）对于坏字符规则的计算，如果每次都去遍历那效率会很低，可以利用一个哈希表，存储每个字符在模式串中的位置，如果有多个相同字符，则取下标最大的一个。如图：

文章插图

文章插图
（2）对于好后缀规则，其核心在于：在模式串中查找与好后缀匹配的子串；在好后缀的所有后缀字串中，查找能与模式串前缀子串匹配的最长子串。

先来解决第一个问题，如何表示模式串中不同的后缀字串以及如何滑动到对应位置？

分析可知，后缀子串的最后一个字符的位置是固定且唯一的，因此只需通过后缀子串的长度即可进行唯一标识。然后引入一个数组suffix，数组下标表示后缀子串的长度（下标唯一且不变，子串最后一个字符的位置唯一且不变），对应数组值表示与其匹配的另一个子串的起始下标。如图：

文章插图
如果存在多个合法的子串，则取下标最大的一个。
—— —— —— —— —— —— —— —— —— —— —— —— —— ——

找完了模式串中的所有子串，还有一个问题：查找在好后缀的所有后缀子串中，能与模式串前缀子串匹配的最长的一个后缀子串（以下记为 “最长可匹配后缀子串”）

同样，为了避免每次遍历带来的时间消耗问题，我们对其也进行预处理。因为已经用数组 suffix 记录了滑动的规则，因此现在只需记录是否需要滑动即可。定义一个bool类型的数组 prefix，记录模式串的每个后缀子串是否能匹配模式串的前缀子串。如图：

文章插图
—— —— —— —— —— —— —— —— —— —— —— —— —— ——

接下来，理解并推导一下这两个数组的值

用模式串的前缀子串，即下标为 [ 0, i ] （ 0 <= i <= m – 2 ）的子串，与整个模式串求公共后缀子串。若公共后缀字串的长度为 k ，在前缀子串中的起始下标为 j ，则记录 suffix[ k ] = j。若 j = 0 ，说明公共后缀子串是模式串的前子串，那就记录prefix[ k ] = true 。相当于将字符串分为两部分，若存在两部分完全相同，则记录为 true 。

文章插图
—— —— —— —— —— —— —— —— —— —— —— —— —— ——

最后来看一下，如何根据这两个数组计算出滑动的位数

设好后缀长度为 k，用好后缀 { u } 在数组 suffix 中查找可匹配子串。若 suffix[ k ] ≠ -1 ，说明存在可匹配字串，则将模式串往后移动 j – suffix[ k ] + 1 位，其中 j 表示坏字符对应模式串中的下标位置。如图：

文章插图
如果 suffix[ k ] = -1，说明模式串中不存在与好后缀匹配的子串。此时，使用好后缀的另一条规则：查找好后缀中，所有后缀子串中，能与模式串前缀子串匹配的，最长的那一个后缀子串。好后缀 pat[ j + 1, m – 1 ]的后缀子串 pat[ r, m – 1]（ j + 2 <= r <= m – 1 ）记作 { v }，其长度 k = m – r 。若 prefix[ k ] = true，表示长度为 k 的后缀子串，存在可匹配的前缀子串 { v* }，则将模式串移动 r 位。如图：