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

复杂度分析：
现在，该算法第一次计算t的哈希值时，时间复杂度为O(n)；后续计算哈希值因为利用了滑窗的优化只有O(1)；比较字符串的Equals()方法，一般地，可以视为O(1) 。

总时间复杂度为O( m + n )，其中计算 next 数组的时间为 O( m )；匹配时时间为 O( n ) 。

空间复杂度为O( m )，使用了一个 next 数组，其中 m 为模式串的长度。

照例，测一下刚才的题

文章插图

文章插图
可以发现，即使面对很高数量级的数据，其效率是RK算法的两倍。
【注意：用此代码提交洛谷的题目（P3375 【模板】KMP字符串匹配 - 洛谷）会存在两个点超时，另一位使用C#提交的Coder也发生了同样的问题。推测可能是运行环境的原因，洛谷上的C#运行环境为C# MONO，其优化与相关底层逻辑并不如现行的 .NET。力扣和牛客使用的运行环境分别是 .NET 6/C# 10 与 mcs5.4，因此一般不会出现卡语言的情况】

文章插图
4. BM算法（Boyer-Moore）【参考文章：字符串匹配算法：KMP与BM - AD_milk - 博客园 (cnblogs.com) 参考书籍：《数据结构与算法之美》】
虽然KMP比较出名，但在效率上有很多的算法都比它要好，如BM算法，其效率要比KMP好上3到4倍。当模式串长度较短时，二者效率基本相近；随着模式串 pat 的长度增大，BM的优势也逐渐凸显出来。原因可能在于，BM属于贪心算法，适应于实际应用，同时，贪心也是思考问题最直接的方式；KMP是稳定算法，中规中矩，按规矩办事，不在乎特例。
首先抛出两个定义：
（1）坏字符规则：指待匹配串和主串当中不匹配的字符，将主串的的该字符定义为坏字符。
BM算法与我们平常接触的字符串比较方法不同，它是按模式串从大到小的顺序，倒着比的。这样做也是有好处的，起码直观上是这样感觉的，贪心也是凭感觉嘛。就像做选择题，出卷老师为了让你花的时间久一点，故意把正确答案放到C跟D上。所以根据统计规律聪明点的做法应该是先算C跟D 。
举个例子：

文章插图
从模式串的末尾开始比较，当前主串的字符 ‘C’ 与模式串的字符 ’D’ ，将其定义为“坏字符”，有该字符存在，则无论之前匹不匹配，模式串均不可能在包含该坏字符的字串内被匹配。

文章插图
俗话说：“三十六计走为上计“，既然你不满足我那我就开溜，直接向后移动6位，从没有坏字符的地方开始匹配。配着配着，发现又不满足了，定义坏字符为 ‘T‘ ，所以继续后移。
据此我们可以发现一个规律：当不匹配时，设坏字符对应的模式串中的字符，在模式串中的下标为 si （相对下标）。若坏字符在模式串中存在，则把这个坏字符在模式串中的下标记为 xi；不存在，则把 xi 记为 -1 。且这样的坏字符在模式串中若存在多个，则总是选择最靠后的一个下标，以此保证不会因滑动过多而略过某些情况。那么，模式串向后滑动的位数 k = si – xi 。图解参阅如下：

文章插图
（2）好后缀规则：指待匹配串和主串当中相匹配的后缀。
利用坏字符规则，BM在最优情况下的时间复杂度为 O( n / m )，例如主串为 aaabaaabaaabaaab，模式串为 aaaa，每次均可向后滑动四位。但只有这一个规则还不够，因为 k 可能为负数，如主串为 aaaaaaaaaaaa，模式串为 baaa 。因此，我们又引入一个规则：好后缀规则。
依旧来举例说明：