有哪些算法惊艳到了你？

Ilingis · 发表于 2021-7-22 09:48

看 KMP 被提了一万遍，特来为 Boyer-Moore 找点存在感
在长度 n 的字符串中寻找长度 m 的子串，Boyer Moore 算法的最优情况时间复杂度是 O(n/m)，最差情况（打上补丁之后）是 O(n)
做到 O(n/m) 的方法特惊艳：从右往左匹配
具体点，假设在 &#34;1234567&#34; 里面查找 &#34;abcd&#34;，一般的算法要比较 &#39;1&#39;!=&#39;a&#39;, &#39;2&#39;!=&#39;a&#39;, &#39;3&#39;!=&#39;a&#39;, &#39;4&#39;!=&#39;a&#39; ... 然鹅 Boyer-Moore 算法只需要做一次字符比较就能得出结论：&#39;4&#39;!=&#39;d&#39;, 所以匹配窗口应该右移4位，越界，所以没有匹配 (当然为了快速得出匹配失败之后窗口最多可以右移多少位的结论需要花 O(m) 的时间预处理模式串 &#34;abcd&#34;)

P.S. 具体算法这里用通俗语言讲得特别清楚：Boyer-Moore algorithm
P.P.S. 好消息好消息 c++17 标准里包含了实现 std::boyer_moore_searcher - cppreference.com

		自动登录	找回密码
密码			立即注册