|
|
KMP算法是一種用于字符串匹配的算法,這個(gè)算法的高效之處在于當(dāng)在某個(gè)位置匹配不成功的時(shí)候可以根據(jù)之前的匹配結(jié)果從模式字符串的另一個(gè)位置開始,而不必從頭開始匹配字符串.
因此這個(gè)算法的關(guān)鍵在于,當(dāng)某個(gè)位置的匹配不成功的時(shí)候,應(yīng)該從模式字符串的哪一個(gè)位置開始新的比較.假設(shè)這個(gè)值存放在一個(gè)next數(shù)組中,其中next數(shù)組中的元素滿足這個(gè)條件:next[j] = k,表示的是當(dāng)模式字符串中的第j + 1個(gè)(這里是遵守標(biāo)準(zhǔn)C語言中數(shù)組元素從0開始的約定,以下不再說明)發(fā)生匹配不成功的情況時(shí),應(yīng)該從模式字符串的第k + 1個(gè)字符開始新的匹配.如果已經(jīng)得到了模式字符串的next數(shù)組,那么KMP算法的實(shí)現(xiàn)如下:
 //?KMP字符串模式匹配算法
//?輸入:?S是主串,T是模式串,pos是S中的起始位置
//?輸出:?如果匹配成功返回起始位置,否則返回-1
int?KMP(PString?S,?PString?T,?int?pos)
   {
 ????assert(NULL?!=?S);
????assert(NULL?!=?T);
????assert(pos?>=?0);
????assert(pos?<?S->length);
????
????if?(S->length?<?T->length)
????????return?-1;
????printf("主串\t?=?%s\n",?S->str);
????printf("模式串\t?=?%s\n",?T->str);
????int?*next?=?(int?*)malloc(T->length?*?sizeof(int));
????//?得到模式串的next數(shù)組
????GetNextArray(T,?next);
????int?i,?j;
????for?(i?=?pos,?j?=?0;?i?<?S->length?&&?j?<?T->length;?)
  ????{
????????//?i是主串游標(biāo),j是模式串游標(biāo)
????????if?(-1?==?j?||????????????????//?模式串游標(biāo)已經(jīng)回退到第一個(gè)位置
????????????S->str[i]?==?T->str[j])?//?當(dāng)前字符匹配成功
????????{
????????????//?滿足以上兩種情況時(shí)兩個(gè)游標(biāo)都要向前進(jìn)一步
????????????++i;
????????????++j;
 ????????}
????????else????????????????????????//??匹配不成功,模式串游標(biāo)回退到當(dāng)前字符的next值
????????{
????????????j?=?next[j];
????????}
????}
????free(next);
????if?(j?>=?T->length)
????{
????????//?匹配成功
????????return?i?-?T->length;
????}
????else
????{
????????//?匹配不成功
????????return?-1;
????}
 }
這是一個(gè)遞推求解的過程,初始的情況是next[0] = -1.
假設(shè)在某一個(gè)時(shí)刻有如下的等式成立:str[0...k-1] = str[j - k...j - 1],那么next[j] = k,在這個(gè)前提下,繼續(xù)進(jìn)行下一個(gè)字符的匹配.
1)如果str[0...k] = str[j - k...j],那么next[j + 1] = next[j] + 1 = k + 1.
2)反之,如果上面的匹配不成立,那么就要從next[k]開始進(jìn)行新的匹配,如果成功的話,那么:
next[j + 1] = next[next[j]] + 1 = next[k] + 1;
如果還是不能匹配成功就再從next[next[k]]的位置開始進(jìn)行的新的匹配,直到匹配成功為止.如果這個(gè)過程一直進(jìn)行下去都沒有找到可以成功匹配的字符的話,那么next[j + 1] = 0,這時(shí)表示要從字符串的第一個(gè)位置開始新的匹配了.
用一個(gè)公式表示上述的算法,那么可以寫作:
next[j] =
1)-1,當(dāng)j = 0時(shí);
2) Max{k | 0 <= k < j && str[0..k - 1] = str[j - k...j - 1]};
3)0,其他情況,此時(shí)匹配要從第一個(gè)位置重新開始.
尋找next數(shù)組的算法如下:
//
?得到字符串的next數(shù)組
void
?GetNextArray(PString?pstr,?
int
?next[])
{
????assert(NULL?
!=
?pstr);?
????assert(NULL?
!=
?next);
????assert(pstr
->
length?
>
?
0
);
????
//
?第一個(gè)字符的next值是-1,因?yàn)镃中的數(shù)組是從0開始的
????next[
0
]?
=
?
-
1
;
????
for
?(
int
?i?
=
?
0
,?j?
=
?
-
1
;?i?
<
?pstr
->
length?
-
?
1
;?)
????
{
????????
//
?i是主串的游標(biāo),j是模式串的游標(biāo)
????????
//
?這里的主串和模式串都是同一個(gè)字符串
????????
if
?(
-
1
?
==
?j?
||
????????????????????????
//
?如果模式串游標(biāo)已經(jīng)回退到第一個(gè)字符
????????????pstr
->
str[i]?
==
?pstr
->
str[j])????
//
?如果匹配成功
????????
{
????????????
//
?兩個(gè)游標(biāo)都向前走一步
????????????
++
i;
????????????
++
j;
????????????
//
?存放當(dāng)前的next值為此時(shí)模式串的游標(biāo)值
????????????next[i]?
=
?j;
????????}
????????
else
????????????????????????????????
//
?匹配不成功j就回退到上一個(gè)next值
????????
{
????????????j?
=
?next[j];
????????}
????}
}
完整的算法如下:
/**/
/*
*******************************************************************
????created:????2006/07/02
????filename:?????KMP.cpp
????author:????????李創(chuàng)
????????????????
http://www.shnenglu.com/converse/
????????????????
????????????????參考資料:?嚴(yán)蔚敏<<數(shù)據(jù)結(jié)構(gòu)>>
????purpose:????KMP字符串匹配算法的演示
********************************************************************
*/
#include?
<
stdio.h
>
#include?
<
stdlib.h
>
#include?
<
assert.h
>
#include?
<
string
.h
>
#define
?MAX_LEN_OF_STR????30????????????
//
?字符串的最大長(zhǎng)度
typedef?
struct
?String????????????????
//
?這里需要的字符串?dāng)?shù)組,存放字符串及其長(zhǎng)度
{
????
char
????str[MAX_LEN_OF_STR];????
//
?字符數(shù)組
????
int
????????length;????????????????????
//
?字符串的實(shí)際長(zhǎng)度
}
String,?
*
PString;
//
?得到字符串的next數(shù)組
void
?GetNextArray(PString?pstr,?
int
?next[])
{
????assert(NULL?
!=
?pstr);?
????assert(NULL?
!=
?next);
????assert(pstr
->
length?
>
?
0
);
????
//
?第一個(gè)字符的next值是-1,因?yàn)镃中的數(shù)組是從0開始的
????next[
0
]?
=
?
-
1
;
????
for
?(
int
?i?
=
?
0
,?j?
=
?
-
1
;?i?
<
?pstr
->
length?
-
?
1
;?)
????
{
????????
//
?i是主串的游標(biāo),j是模式串的游標(biāo)
????????
//
?這里的主串和模式串都是同一個(gè)字符串
????????
if
?(
-
1
?
==
?j?
||
????????????????????????
//
?如果模式串游標(biāo)已經(jīng)回退到第一個(gè)字符
????????????pstr
->
str[i]?
==
?pstr
->
str[j])????
//
?如果匹配成功
????????
{
????????????
//
?兩個(gè)游標(biāo)都向前走一步
????????????
++
i;
????????????
++
j;
????????????
//
?存放當(dāng)前的next值為此時(shí)模式串的游標(biāo)值
????????????next[i]?
=
?j;
????????}
????????
else
????????????????????????????????
//
?匹配不成功j就回退到上一個(gè)next值
????????
{
????????????j?
=
?next[j];
????????}
????}
}
//
?KMP字符串模式匹配算法
//
?輸入:?S是主串,T是模式串,pos是S中的起始位置
//
?輸出:?如果匹配成功返回起始位置,否則返回-1
int
?KMP(PString?S,?PString?T,?
int
?pos)
{
????assert(NULL?
!=
?S);
????assert(NULL?
!=
?T);
????assert(pos?
>=
?
0
);
????assert(pos?
<
?S
->
length);
????
????
if
?(S
->
length?
<
?T
->
length)
????????
return
?
-
1
;
????printf(
"
主串\t?=?%s\n
"
,?S
->
str);
????printf(
"
模式串\t?=?%s\n
"
,?T
->
str);
????
int
?
*
next?
=
?(
int
?
*
)malloc(T
->
length?
*
?
sizeof
(
int
));
????
//
?得到模式串的next數(shù)組
????GetNextArray(T,?next);
????
int
?i,?j;
????
for
?(i?
=
?pos,?j?
=
?
0
;?i?
<
?S
->
length?
&&
?j?
<
?T
->
length;?)
????
{
????????
//
?i是主串游標(biāo),j是模式串游標(biāo)
????????
if
?(
-
1
?
==
?j?
||
????????????????
//
?模式串游標(biāo)已經(jīng)回退到第一個(gè)位置
????????????S
->
str[i]?
==
?T
->
str[j])?
//
?當(dāng)前字符匹配成功
????????
{
????????????
//
?滿足以上兩種情況時(shí)兩個(gè)游標(biāo)都要向前進(jìn)一步
????????????
++
i;
????????????
++
j;
????????}
????????
else
????????????????????????
//
??匹配不成功,模式串游標(biāo)回退到當(dāng)前字符的next值
????????
{
????????????j?
=
?next[j];
????????}
????}
????free(next);
????
if
?(j?
>=
?T
->
length)
????
{
????????
//
?匹配成功
????????
return
?i?
-
?T
->
length;
????}
????
else
????
{
????????
//
?匹配不成功
????????
return
?
-
1
;
????}
}
|