V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
mengzhuo
V2EX  ›  编程

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

  •  
  •   mengzhuo · 2015-03-07 00:14:34 +08:00 · 3478 次点击
    这是一个创建于 3534 天前的主题,其中的信息可能已经有所发展或是发生改变。
    9 条回复    2015-03-19 10:00:07 +08:00
    illuz
        1
    illuz  
       2015-03-07 00:33:37 +08:00
    看了一下,跟 KMP 一样神奇
    mengzhuo
        3
    mengzhuo  
    OP
       2015-03-07 15:41:35 +08:00
    @illuz

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

    @cbwzwsq
    看过了,但是解释得不清楚
    illuz
        4
    illuz  
       2015-03-07 19:51:45 +08:00
    @mengzhuo 看了一下 Sunday 算法,也是很酷啊
    mulog
        5
    mulog  
       2015-03-18 19:01:47 +08:00
    demo 有bug誒?
    boyer_moore("dd", "dddddd") 只輸出 [0, 2, 4]
    感覺是 40行 index 不該是那樣變動的
    mengzhuo
        6
    mengzhuo  
    OP
       2015-03-18 21:47:57 +08:00
    @mulog
    这是对的,子字段确实只匹配0,2,4
    你的预期不会是0,1,2,3,4吧……
    mulog
        7
    mulog  
       2015-03-18 23:08:45 +08:00
    @mengzhuo
    囧了 是的。。。 请问这是个约定俗成的规则吗? 不考虑 overlapping 的匹配?
    因为我 google 了一下似乎没看到相关说明
    以及当时搜到了一个 UT Dallas 的 这个算法的 demo,他是找出了所有匹配的,即0 1 2 3 4...
    mulog
        8
    mulog  
       2015-03-18 23:09:40 +08:00
    mengzhuo
        9
    mengzhuo  
    OP
       2015-03-19 10:00:07 +08:00
    @mulog
    你好仔细,自愧不如中……

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

    当然,如果需求是要匹配overlapping的项的话,肯定得按demo里的走了。
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   5402 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 27ms · UTC 07:24 · PVG 15:24 · LAX 23:24 · JFK 02:24
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.