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

[mengzhuo]

https://www.youtube.com/watch?v=PHXAOKQk2dw

然后我按讲解写的demo
https://gist.github.com/mengzhuo/d713cb8be6c871995b79

[illuz]

看了一下，跟 KMP 一样神奇

[cbwzwsq]

http://en.wikipedia.org/wiki/Boyer%E2%80%93Moore%E2%80%93Horspool_algorithm

[mengzhuo]

@illuz

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

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

[illuz]

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

[mulog]

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

[mengzhuo]

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

[mulog]

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

[mulog]

@mengzhuo
忘了放那个 demo 的 link
http://www.utdallas.edu/~besp/demo/John2010/boyer-moore.htm

[mengzhuo]

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

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

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