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

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

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

设好后缀长度为 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 位。如图：

文章插图
如果在模式串中没有找到与好后缀可以匹配的前缀子串，也没有找到好后缀中可匹配模式串中前缀子串的，后缀子串，则将整个模式串后移 m 位。如图：

文章插图
—— —— —— —— —— —— —— —— —— —— —— —— —— ——
代码实现：【注：考虑到时间成本与篇幅问题，在此不做BM算法的同意主串多次匹配问题，如有兴趣欢迎自行研究，本人也可能会在今后放出可对同一主串多次匹配的代码】

文章插图
复杂度分析：

时间复杂度为O( n ) 若模式串中包含大量重复字符，则计算两个数组的时间将会达到 O( m2 ) ，但一般不会出现这样的极端情况。

空间复杂度为O( m )

文章插图
这就是一种极端情况，存在大量重复字符，导致其效率严重下降。
总结—— —— —— —— —— —— —— —— —— —— —— —— —— ——
—— —— —— —— —— —— —— —— —— —— —— —— —— ——
至此，四种匹配方法全部介绍完毕，总结一下：
1. BF纯暴力算法，一位以为比较，遇到不匹配的从模式串开头在此一位一位比较。时间复杂度较高，但简洁明了思路清晰，因此在实际应用中最为常用。
2. RK算法，基于BF的比较字符的思想，转化为比较子串的哈希值。数值间的比较确实比字符比较快，而且利用滑窗的思想将计算哈希的时间复杂度将为 O( n ) ，但容易存在哈希冲突的问题，冲突后需要对两部分子串进行完整比较。计算哈希方式越简单、字符串越长，冲突的概率越高，复杂度也会接近 O( n2 ) 。
3. KMP算法，利用某一特殊的规律，减少在不匹配时向后退回的位数，以达到降低时间复杂度的目的。
4. BM算法，结合贪心思想，进一步对KMP进行优化。但这两种方法过于复杂，掌握很不容易。