posts - 4,  comments - 2,  trackbacks - 0
 
KMP中的主串指针不用回溯,下面的串匹配怎么进行:请教一下
位数:    1  2  3  4  5
主串:    a  a   a  a  b
模式串: a  a   a  b
 如果主串指针不用回溯,可以发现主串包含模式串么?想不明白。
posted on 2010-07-30 10:35 ypp 阅读(209) 评论(2)  编辑 收藏 引用 所属分类: c++

FeedBack:
# re: 请教一下 关于串匹配的KMP算法问题
2010-07-31 09:21 | Luo Huiming
KMP是通过一个next的量求得主串与模式串不匹配时模式串下一个应与主串当前位置进行匹配的位置,从而达到主串指针不回溯的。next[i]其实相当于对于模式串前i-1个字符的不包含自己的一个最长前缀与最长后缀相同的长度+1.
上面那个是第四个位置
a a a a b
a a a b
那么a a a的一个最长前缀与最长后缀是a a,那么当前上前的第四个a应该再与模式串的第三个位置(a a的长度+1)进行匹配。  回复  更多评论
  
# re: 请教一下 关于串匹配的KMP算法问题
2010-07-31 11:48 | smztsmzt
@Luo Huimin
感谢  回复  更多评论
  

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理



<2010年7月>
27282930123
45678910
11121314151617
18192021222324
25262728293031
1234567

常用链接

留言簿

随笔分类(4)

随笔档案(4)

搜索

  •  

最新评论

阅读排行榜

评论排行榜