/*
data:2007 -1 - 7 by:snowhill
char *s="abcdefhighcbcccfghiabcdefghikl";
char *T="cbcbc"; next[]的值应为: -1,0,0,1,2
如果char *T="cbccc";next[]的值应为: -1,0,0,1,1
next[]的求法相当于T自身的一个模式匹配
在KMP_Find()中 如果J的值大于T的长度则查找成功
*/
#include
"
iostream.h
"
int
length(
char
*
s)
{
int
i
=
0
;
while
(s[i]
!=
NULL)
i
++
;
return
i;
}
void
get_next(
char
*
T,
int
*
next)
{
int
i
=
0
, j
=-
1
;
next[
0
]
=-
1
;
while
(i
<
length(T))
{
if
(j
==-
1
||
T[i]
==
T[j])
{
++
i;
++
j;
cout
<<
"
i=
"
<<
i
<<
"
j=
"
<<
j
<<
endl;
next[i]
=
j;
}
else
j
=
next[j];
}
//
end while
for
(
int
l
=
0
;l
<
length(T);l
++
)
cout
<<
next[l]
<<
"
\t
"
;
cout
<<
endl;
}
//
KMP算法
void
KMP_Find(
char
*
s,
char
*
T)
{
int
i
=
0
, j
=
0
,k
=
length(s);
cout
<<
"
k=
"
<<
k
<<
endl;
int
*
next
=
new
int
[k];
get_next(T,next);
while
(i
<
k)
{
if
(j
=-
1
||
s[i]
==
T[j]){
++
i;
++
j; }
else
j
=
next[j];
}
if
(j
>=
length(T)) cout
<<
"
查找完毕!未找到
"
<<
endl;
else
cout
<<
"
查找成功!
"
;
}
/*
原始查找算法
*/
void
find(
char
*
s,
char
*
T)
{
int
i
=
0
,j
=
0
,k
=
length(s);
if
(j
<
length(T)
&&
i
<
k)
{
if
(s[i]
==
T[j])
{
j
++
;
i
++
;
}
else
{i
=
i
-
j
+
1
;j
=
0
;}
}
if
(j
=
length(T)
-
1
)
cout
<<
"
find is sucess!
"
<<
endl;
else
cout
<<
"
error!
"
<<
endl;
}
/*
测试函数
*/
void
main()
{
char
*
s
=
"
abcdefhighcbcccfghiabcdefghikl
"
;
char
*
T
=
"
cbcbc
"
;
find(s,T);
KMP_Find(s,T);
}