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 阅读(227) 评论(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
感谢回复更多评论

刷新评论列表

只有注册用户登录后才能发表评论。
【推荐】100%开源！大型工业跨平台软件C++源码提供，建模，组态！

相关文章: 关于稀疏矩阵相乘——转化为一维矩阵请教一下关于串匹配的KMP算法问题

网站导航: 博客园 IT新闻 BlogJava 博问 Chat2DB 管理

2010年7月

日

一

二

三

四

五

六

常用链接

留言簿

随笔分类(4)

随笔档案(4)

搜索

最新评论

阅读排行榜

评论排行榜