关于模式匹配（KMP）算法 — 编程爱好者社区

您所在位置：社区首页 — 数据结构与算法 — 关于模式匹配（KMP）算法

主题：关于模式匹配（KMP）算法

stuman [专家分：0] 发布于 2006-05-30 20:10:00

现有主串000000001,模式串0001.那么模式串的next[4]应该是几?我觉得应该是4,但是如果这样的话模式串将无法向右移动,而永远停留在主串的第4个字符与模式串的第4个字符间比较,请问正确的说法是什么?

沙发

海上飞洪 [专家分：520] 发布于 2006-05-31 00:39:00

这个算法具体可以看<严蔚敏数据结构>的第84页

板凳

boxertony [专家分：23030] 发布于 2006-06-02 12:21:00

怎么也不可能是4啊。应该是-1

3 楼

nevsaynevwk [专家分：0] 发布于 2006-06-16 08:50:00

应该是3

4 楼

stuman [专家分：0] 发布于 2006-06-16 17:39:00

请问楼上是怎么算出来的？

5 楼

nevsaynevwk [专家分：0] 发布于 2006-06-16 19:59:00

      j=  1 2 3 4
模式串    0 0 0 1
next[j]=  0 1 2 3

6 楼

boxertony [专家分：23030] 发布于 2006-06-18 11:45:00

[quote]
      j=  1 2 3 4
模式串    0 0 0 1
next[j]=  0 1 2 3[/quote]

这个结果虽然也还可以，但不如
-1 -1 -1 3

抱歉，我前面的也说错了，应该是3。

您尚未登录，请登录后再回复。点此登录或注册