我的c++—思考的芦苇
C++博客
首页
新文章
新随笔
聚合
管理
posts - 4, comments - 2, trackbacks - 0
请教一下 关于串匹配的KMP算法问题
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
知识库
博问
管理
<
2009年8月
>
日
一
二
三
四
五
六
26
27
28
29
30
31
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
1
2
3
4
5
常用链接
我的随笔
我的评论
我参与的随笔
留言簿
给我留言
查看公开留言
查看私人留言
随笔分类
(4)
c++(2)
DataRecovery
my life+my thought(2)
随笔档案
(4)
2010年8月 (1)
2010年7月 (1)
2010年6月 (1)
2009年8月 (1)
搜索
最新评论
1. re: 请教一下 关于串匹配的KMP算法问题
@Luo Huimin
感谢
--smztsmzt
2. re: 请教一下 关于串匹配的KMP算法问题
评论内容较长,点击标题查看
--Luo Huiming
阅读排行榜
1. 关于稀疏矩阵相乘——转化为一维矩阵(474)
2. 享受编程(304)
3. 请教一下 关于串匹配的KMP算法问题 (227)
4. R-studio对硬盘的分析(186)
评论排行榜
1. 请教一下 关于串匹配的KMP算法问题 (2)
2. 关于稀疏矩阵相乘——转化为一维矩阵(0)
3. 享受编程(0)
4. R-studio对硬盘的分析(0)