迄今为止我看过最好的 Boyer Moore 讲解

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

这是一个创建于 3584 天前的主题，其中的信息可能已经有所发展或是发生改变。

9 条回复 • 2015-03-19 10:00:07 +08:00

illuz

2015-03-07 00:33:37 +08:00

看了一下，跟 KMP 一样神奇

cbwzwsq

2015-03-07 11:20:23 +08:00

mengzhuo

2015-03-07 15:41:35 +08:00

@illuz

比KMP在特定条件下快啊啊哈哈哈
而且把偏移值加一就是Sunday算法了

@cbwzwsq
看过了，但是解释得不清楚

illuz

2015-03-07 19:51:45 +08:00

@mengzhuo 看了一下 Sunday 算法，也是很酷啊

mulog

2015-03-18 19:01:47 +08:00

demo 有bug誒？
boyer_moore("dd", "dddddd") 只輸出 [0, 2, 4]
感覺是 40行 index 不該是那樣變動的

mengzhuo

2015-03-18 21:47:57 +08:00

@mulog
这是对的，子字段确实只匹配0，2，4
你的预期不会是0，1，2，3，4吧……

mulog

2015-03-18 23:08:45 +08:00

@mengzhuo
囧了是的。。。请问这是个约定俗成的规则吗？不考虑 overlapping 的匹配？
因为我 google 了一下似乎没看到相关说明
以及当时搜到了一个 UT Dallas 的这个算法的 demo，他是找出了所有匹配的，即0 1 2 3 4...

mulog

2015-03-18 23:09:40 +08:00

mengzhuo

2015-03-19 10:00:07 +08:00

@mulog
你好仔细，自愧不如中……

两者差在，你帖子里demo的算法并没有跳过整个匹配项，只按好字符移动。
那么必然速度就慢多了。

当然，如果需求是要匹配overlapping的项的话，肯定得按demo里的走了。