Posted on 2006-10-21 20:27
魔のkyo 阅读(380)
评论(0) 编辑 收藏 引用 所属分类:
Programming
#define
B_MAX_LEN 2000
int
next[B_MAX_LEN];
void
Compute_Next(
char
B[]){
int
i;
next[
0
]
=
next[
1
]
=
0
;
for
(i
=
2
;B[i];i
++
){
int
j
=
next[i
-
1
];
while
(B[i
-
1
]
!=
B[j]
&&
j
>
0
)
j
=
next[j];
if
(B[i
-
1
]
==
B[j])
next[i]
=
j
+
1
;
else
next[i]
=
0
;
}
}
//
串匹配的KMP算法
//
返回A中第一个与B匹配的子串的指针，若找不到则返回NULL
//
需要已经对串B计算好next[]
char
*
String_Match(
char
A[],
char
B [])
{
int
i
=
0
,j
=
0
;
while
(A[i]
&&
B[j]){
if
(A[i]
==
B[j]){
++
i;
++
j;
}
else
{
if
(j
==
0
)
++
i;
else
if
(
!
B[j])
break
;
else
j
=
next[j];
}
}
if
(
!
B[j])
return
&
A[i
-
j];
else
return
NULL;
}