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