| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 1341 人关注过本帖
标题:求助!——>数据结构 KMP-next[j]问题
只看楼主 加入收藏
202x
Rank: 1
等 级:新手上路
帖 子:2
专家分:0
注 册:2005-4-21
收藏
 问题点数:0 回复次数:9 
求助!——>数据结构 KMP-next[j]问题
已知模式串='ababaabab', 则next[j]=______。
搜索更多相关主题的帖子: 数据结构 next ababaabab 模式 
2006-02-23 16:45
jzb929
Rank: 1
等 级:新手上路
帖 子:6
专家分:0
注 册:2006-4-12
收藏
得分:0 
011232234
2006-04-27 11:00
jzb929
Rank: 1
等 级:新手上路
帖 子:6
专家分:0
注 册:2006-4-12
收藏
得分:0 
我也刚学
应该对吧
2006-04-27 11:02
菜鸟上路
Rank: 4
等 级:贵宾
威 望:14
帖 子:1120
专家分:0
注 册:2006-3-21
收藏
得分:0 
next[j]这个问题一直很头痛

2006-04-27 12:18
luyx66
Rank: 1
等 级:新手上路
帖 子:28
专家分:0
注 册:2006-3-29
收藏
得分:0 
2楼的好像````````````
这个题好像应该是
011234234吧
2006-04-27 12:44
starrysky
Rank: 16Rank: 16Rank: 16Rank: 16
来 自:华中科技大学EI -T0405
等 级:版主
威 望:11
帖 子:602
专家分:1
注 册:2005-9-12
收藏
得分:0 
应该是 011234234

我的征途是星辰大海
2006-04-27 15:08
starrysky
Rank: 16Rank: 16Rank: 16Rank: 16
来 自:华中科技大学EI -T0405
等 级:版主
威 望:11
帖 子:602
专家分:1
注 册:2005-9-12
收藏
得分:0 
以下是引用菜鸟上路在2006-4-27 12:18:00的发言:
next[j]这个问题一直很头痛

实际上是有个诀窍的,说白了很简单
就以
a b a b a a b a b
0 1 1 2 3 4 2 3 4
为例
next[j] 里面 开头的红色01 没什么好说的,固定格式.
我就以兰色的4 来说明下为什么是4.
与4有关的, 是4所对应的兰色a之前的所有的字符,即紫色的 a b a b a
这个字符串中所有符合匹配条件的字符串如下
a b a b a a b a b a
a a
a b a a b a 最长的匹配字符串(a b a b a本身除外)在这里 ,长度为3, 再加上1,就是4
注意next[ j ]中4 的位置! 至于为什么要加1 ,大家自己去思考吧, 明白了为什么要加1,KMP算法也就自然明白了
next[ j ]中其他位置的数值也可以用同样的方法得出
再找几个例子用这个方法试下吧, 绝对百试百灵




[此贴子已经被作者于2006-4-27 15:56:42编辑过]


我的征途是星辰大海
2006-04-27 15:55
starrysky
Rank: 16Rank: 16Rank: 16Rank: 16
来 自:华中科技大学EI -T0405
等 级:版主
威 望:11
帖 子:602
专家分:1
注 册:2005-9-12
收藏
得分:0 
严蔚敏版数据结构书上例子
a b a a b c a c
0 1 1 2 2 3 1 2

我的征途是星辰大海
2006-04-27 16:02
jzb929
Rank: 1
等 级:新手上路
帖 子:6
专家分:0
注 册:2006-4-12
收藏
得分:0 

谢谢啊
明白了

2006-05-24 16:02
菜鸟上路
Rank: 4
等 级:贵宾
威 望:14
帖 子:1120
专家分:0
注 册:2006-3-21
收藏
得分:0 
这份帖都忘看了,谢谢jzb929能找到这么早的帖,谢谢starryskyl了

2006-05-24 17:47
快速回复:求助!——>数据结构 KMP-next[j]问题
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.046561 second(s), 7 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved