看了两三天的KMP算法,一直看的迷迷糊糊的.现在把这些资料贴在这里...以备日后之需
1.串的模式匹配的改进算法(这个网站对我的理解帮助很大,特别是右边的那块说明部分,以前自己脑筋老是转不过来) http://cist.dhu.edu.cn/kejian/%CA%FD%BE%DD%BD%E1%B9%B9%BE%AB%C6%B7%BF%CE%B3%CC/%D4%DA%CF%DF%D1%A7%CF%B0/text/chapter04/section3/c5.htm
2.KMP 算法的注记 http://www.cublog.cn/u/20/showart_136705.html
3.KMP算法中推导next[],nextval[]--手记 http://jiasimon040510.t8log.ccut.cn/blog-htm-do-showone-tid-6983.html
4.算法原理:
在匹配过和中,当主串中第i个字符与模式串中第j个字符“失配”时(s[i]!=t[j]),将模式串尽量向右移动,让模式串中第k(k<j)个字符与si对齐继续比较,
要让这个条件成立,那么在k之前的k个t字符[0 到 k-1]必须在i之前的k个s字符[i-k 到 i-1]相匹配即:
t[0, 1, 2...k-1] == s[i-k, i-k+1, i-k+2...i-1] ---(1)
而由之前的部分匹配成功的结果可知:
t[0, 1, 2...j-1] == s[i-j, i-j+1, i-j+2...i-1] ---(2)
==>
t[j-k, j-k+1, j-k+2...j-1] == s[i-k, i-k+1, i-k+2...i-1] --(3)
由(1)与(3)可得:
t[0, 1, 2...k-1] == t[j-k, j-k+1, j-k+2...j-1] ---(4)
求出k值,就是next[j]的值了
总之,相对我来说,算法不是很好懂.但是大家看到我这么笨的人到最后都能明白一二.大家就更没有理由看不懂了,祝大家成功附上我的测试源码:
#include
<
iostream
>
using
namespace
std;
void
GetNext(
char
t[],
int
next[])
{
int
j
=
0
;
int
k
=
-
1
;
next[j]
=
k;
int
tlen
=
strlen(t);
while
(j
<
tlen)
{
if
(k
==
-
1
||
t[j]
==
t[k])
{
j
++
;
k
++
;
if
(t[j]
==
t[k])
{
next[j]
=
next[k];
}
else
next[j]
=
k;
}
else
{
k
=
next[k];
}
}
}
int
KMP(
char
s[],
char
t[],
int
pos,
int
next[])
{
int
slen
=
strlen(s);
int
tlen
=
strlen(t);
int
i
=
0
;
int
j
=
0
;
while
(i
<
slen
&&
j
<
tlen)
{
if
(j
==
-
1
||
s[i]
==
t[j])
{
i
++
;
j
++
;
}
else
{
j
=
next[j];
}
}
if
(j
==
tlen)
{
return
i
-
tlen;
}
else
return
-
1
;
}
int
main (
int
argc,
char
**
argv)
{
char
s[]
=
"
aaaabaabaaabaaabaaaaabaaabaaabaaabaaabaaabaaabaaabaaabaaabacb
"
;
char
t[]
=
"
aabaaa
"
;
int
next[
20
]
=
{
0
}
;
GetNext(t, next);
for
(
int
i
=
0
; i
<
20
; i
++
)
cout
<<
"
next[
"
<<
i
<<
"
]:
"
<<
next[i]
<<
endl;
cout
<<
KMP(s, t,
0
, next)
<<
endl;
}
posted @
2006-11-10 01:51 猪头饼 阅读(1434) |
评论 (0) |
编辑 收藏