jake1036
My Links
C++博客
首页
新随笔
联系
聚合
管理
Blog Stats
Posts - 101
Stories - 0
Comments - 23
Trackbacks - 0
常用链接
我的随笔
我的评论
我参与的随笔
留言簿
(1)
给我留言
查看公开留言
查看私人留言
随笔分类
c++学习总结(7)
(rss)
larbin源码分析(4)
(rss)
算法相关(65)
(rss)
随笔档案
2011年9月 (4)
2011年8月 (1)
2011年7月 (5)
2011年6月 (24)
2011年5月 (34)
2011年4月 (10)
2011年3月 (4)
2010年12月 (1)
2010年11月 (7)
2010年10月 (5)
2010年9月 (5)
2010年8月 (1)
搜索
最新评论
1. re: 01背包问题总结(一)http://www.cppblog.com/Modules/CaptchaImage/JpegImage.aspx
评论内容较长,点击标题查看
--http://www.cppblog.com/Modules/CaptchaImage/JpegIm
2. re: 编程之美-2.5寻求最大的K个数[未登录]
你确定以上代码可以运行?
呵呵
--xixi
3. re: larbin源码分析(七) larbin中的2种容器与4个url队列
评论内容较长,点击标题查看
--Humton
4. re: larbin源码分析(七) larbin中的2种容器与4个url队列
评论内容较长,点击标题查看
--Humton
5. re: 动态规划法-------最大连续子序列和
@123
谁说的,明明b[7] == 25好吧
--456
阅读排行榜
1. 01背包问题总结(一)(24969)
2. 动态规划法-------最大连续子序列和(9579)
3. c++类模板学习(8013)
4. 完全背包问题 <二>(4481)
5. 编程之美1.8-----电梯调度算法(4132)
评论排行榜
1. 2011-4-16 淘宝实习生面试总结(6)
2. 动态规划法-----最长增序子序列(非连续)(3)
3. 动态规划法-------最大连续子序列和(3)
4. 面试100 34找出数组中唯一出现一次的两个数字(2)
5. larbin源码分析(七) larbin中的2种容器与4个url队列(2)
KMP算法
KMP算法
算法实质是发现不匹配的位时,只移动模式串j,
前缀函数par[k] 实际上是找出模式串P中从1--k位置上的一个位置q
使par[1 q]为par[1 k]的最大前缀,
par[k-q+1 k]为par[1 k]的最大后缀,
而且需要满足一个条件,即par[1 q] == par[k-q+1 k]
使用这个前缀数组,有一个好处,就是模式串P,不需要每次查找失败时,都从初始位置处开始重新匹配。
若P[q+1] != T[i] ,则只需要重新使q = par[q]。因为模式串的最长后缀与最长的前缀相同,所以不需要从最开始的位置开始移动。
只需要移动到par[q]处。 然后继续 P[q+1]与T[i]比较,不相等则重复此过程。
很可能q移动到0处,仍然不相同。这时候外层查找串T下标i进行自增。然后重复之前的操作
二 前缀数组的求法
另外一个问题就是par这个前缀数组如何确定
实际上这是一个模式串P自身匹配的过程。复杂度为o(M),从2----m,逐个确定 par[i]
两者都有一个共同的特点。若当p[i] != p[q+1]时,需要迭代q = par[q] ,直到q==0 或者得到p[q+1] != p[i]时为止。
每一次循环确定一个par[i].
代码如下:
#include
<
iostream
>
#include
<
cstring
>
using
namespace
std ;
int
par[
20
] ;
//
作为前缀数组
void
iniPar(
char
*
P ,
int
*
par ,
int
m)
{
//
构造字符串的前缀,实质上是字符串P的自我匹配
par[
1
]
=
0
;
int
i , j , q
=
0
;
for
(i
=
2
; i
<
m ; i
++
)
{
while
(q
>
0
&&
P[i]
!=
P[q
+
1
])
q
=
par[q] ;
if
(P[i]
==
P[q
+
1
])
q
++
;
par[i]
=
q ;
}
}
int
main()
{
char
T[
100
]
=
"
0bacbabababacaab
"
;
char
P[
20
]
=
"
0ababaca
"
;
int
m
=
strlen(P) ;
int
n
=
strlen(T) ;
int
q
=
0
;
//
表示当前P串正在比较的位置
int
i , j , k ;
iniPar(P , par , m) ;
//
构造前缀数组,实际上是P串的自我匹配,比较和P与T串的匹配相似
for
(i
=
1
; i
<
n ; i
++
)
{
while
(q
>
0
&&
P[q
+
1
]
!=
T[i]) q
=
par[q] ;
//
则把P串左移
if
(P[q
+
1
]
==
T[i])
//
如果当前匹配的相等,则继续移动p串
q
++
;
if
(q
==
m
-
1
)
{
printf(
"
%d\n
"
, i
-
(m
-
1
)
+
1
) ;
q
=
par[q] ;
//
继续寻找下一个
}
}
for
(i
=
1
; i
<
m ;i
++
)
printf(
"
%d
"
, par[i]) ;
system(
"
pause
"
) ;
return
0
;
}
posted on 2011-05-05 20:33
kahn
阅读(363)
评论(0)
编辑
收藏
引用
所属分类:
算法相关
只有注册用户
登录
后才能发表评论。
相关文章:
9-24MTK一面二面
微软笔试总结
2011-09-07xx移动创业公司笔试题
编程之美2.7 最大公约数
O(n)实现删除两个数组中的共同元素
编程之美1.9(二) 高效率地安排会面
分组背包问题(六)
二维背包问题(五)
多重背包(三)
完全背包问题 <二>
网站导航:
博客园
IT新闻
BlogJava
知识库
博问
管理
Powered by:
C++博客
Copyright © kahn