KMP算法的詳細(xì)解釋及實(shí)現(xiàn)

這是我自己學(xué)習(xí)算法時(shí)有關(guān)KMP的學(xué)習(xí)筆記，代碼注釋的十分的詳細(xì)，分享給大家，希望對(duì)大家有所幫助 在介紹KMP算法之前，

先來(lái)介紹一下樸素模式匹配算法：

樸素模式匹配算法：

假設(shè)要從主串S=”goodgoole”中找到T=”google”這個(gè)字串的位置，我們需要一下的步驟：

1，主串S的第一位開(kāi)始，S與T的前三個(gè)字母都能成功匹配，但是S的第四個(gè)字母是d，而T的第四位是g，所以主串S的第一位匹配失敗

2，然后從主串的第二位開(kāi)始，會(huì)發(fā)現(xiàn)主串的第二位字母與T的第一位字母不同，所以匹配失敗，然后再?gòu)闹鞔牡谌婚_(kāi)始，

3，經(jīng)過(guò)這樣的依次嘗試后，之到主串的第五位開(kāi)始，S與T的6個(gè)字母完全匹配成功

該樸素模式匹配算法的代碼實(shí)現(xiàn)是：

該算法的功能是返回字串T在主串S中第pos個(gè)字符之后的位置，若不存在，則函數(shù)返回值為0，前提是T非空且1<pos<StrLength(S)

int Index(char* S,char* T,int pos)//index是索引的意思

{

int i=pos-1;//i用于主串S中當(dāng)前位置的下標(biāo),S[0]是主串T的第一個(gè)字符

int j=0;//j用于子串T中當(dāng)前位置下標(biāo)值，即T[0]是字串T的第一個(gè)字符

while(i<strlen(S)&&j<strlen(T))

{

if(S[i]==T[j])//如果主串S當(dāng)前的字母與子串的字母相等則繼續(xù)

{

++i;

++j;

}

else

{

i=i-j+1;//eg:如果第一次匹配時(shí)，不相等則使i=i-j+2=i+1;即向下走一個(gè)字母，以i=0為例，剛開(kāi)始從主串第一個(gè)位置開(kāi)始，如果S[i]==T[j]一直滿(mǎn)足，則i和j同步變化，即i=j;一旦有不相等的字母時(shí)，i=i-j+1,實(shí)際就是i=1；然后再?gòu)闹鞔牡诙€(gè)字母開(kāi)始

j=0;//重新匹配時(shí)，j又回到T的子串的首位

}

}

if(j==strlen(T))//此時(shí)已完成匹配

return i-strlen(T);//返回

else

return 0;

}

KMP模式匹配算法

KMP算法中把T串各個(gè)位置的j值的變化定義為一個(gè)數(shù)組next，那么next的長(zhǎng)度就是T串的長(zhǎng)度；

next數(shù)組值得推導(dǎo)：

T="abcdex";(前后綴一個(gè)字符相等，k值是2，兩個(gè)字符相等，k值是3，n個(gè)k值相等k值就是就是n+1)

1,當(dāng)j=1時(shí)，next[1]=0;

2,當(dāng)j=2時(shí)，j由1到j(luò)-1只有字符"a",next[2]=1;

3,當(dāng)j=3時(shí)，j由1到j(luò)-1就只有字符串"ab"，顯然"a"與"b"不相等，所以next[3]=1;

4,同理得：T串的next[j]為011111;

T="ababaaaba";

1,當(dāng)j=1時(shí)，next[1]=0;

2,當(dāng)j=2時(shí)，next[2]=1;

3,當(dāng)j=3時(shí)，next[3]=1;

4,當(dāng)j=4時(shí)，next[4]=2;//j由1到j(luò)-1的串是"aba",前綴字符"a"與后綴字符"a"相等，next[4]=2;

5,當(dāng)j=5時(shí)，next[5]=3;//串是"abab",前綴是"ab",后綴是"ab",有兩個(gè)相同的字符，所以為3

6,當(dāng)j=6時(shí)，next[6]=4;//串是"ababa",前綴是"aba"，后綴是"aba",有三個(gè)相同的字符，所以為4

7,當(dāng)j=7時(shí)，next[7]=2;//串是"ababaa",前綴字符是"a"與后綴字符"a"相等，有兩個(gè)相同的字符，所以為2

8,當(dāng)j=8時(shí)，next[8]=2;//串是"ababaaa",前綴字符是"a"與后綴字符"a"相等，有兩個(gè)相同的字符，所以為2

9,當(dāng)j=9時(shí)，next[9]=3;//串是"ababaaab",前綴字符是"ab",后綴字符也為"ab",有兩個(gè)相同的字符，所以為3

10,當(dāng)j=10時(shí)，next[10]=4;//串是"ababaaaba",前綴字符是"aba",后綴字符也為"aba",有三個(gè)相同的字符，所以為4

KMP模式匹配算法實(shí)現(xiàn)

1，通過(guò)計(jì)算返回子串T的next數(shù)組

void get_next(char* T,int *next)

{

　 int i,j;

　　 　i=1;

　j=0;

　　　next[1]=0;

　　 while(i<=strlen(T))

　　{

　　if(j==0||T[i-1]==T[j-1])

{

++i;

++j;

next[i]=j;

}//以T="abcdex"為例：該循環(huán)的執(zhí)行順序:第一步,j=0,執(zhí)行,（i=2,j=1,next[2]=1）第二步，不符合循環(huán)條件，j=next[1]=0,j又變?yōu)?為了再次進(jìn)入循環(huán)，(i=3,j=1,next[3]=1)依次往下循環(huán)

else

j=next[j];

}

}

//這段代碼的目的就是為了計(jì)算出當(dāng)前要匹配的串T的next數(shù)組

int Index_KMP(char* S,char* T,int pos)

{

int i=pos;

int j=1;

int next[255];

get_next(T,next);

while(i<=strlen(S)&&j<=strlen(T))

{

if(j==0||S[i-1]==T[j-1])

{

++i;

++j;

}

else

j=next[j];//起到回溯的作用

}

if(j>strlen(T))

return (i-strlen(T)-1);

else

return 0;

}

附加一個(gè)實(shí)例：

#include<iostream>

using namespace std;

void get_next(char* T,int *next)

{

int i,j;

　　 i=1; j=0;

　　next[1]=0;

　while(i<=strlen(T))

{

if(j==0||T[i-1]==T[j-1])

{　　　　　　　　　　　　　

　　　　　　　 ++i;

++j;

next[i]=j;

}//以T="abcdex"為例：該循環(huán)的執(zhí)行順序:第一步,j=0,執(zhí)行,（i=2,j=1,next[2]=1）第二步，不符合循環(huán)條件，j=next[1]=0,j又變?yōu)?為了再次進(jìn)入循環(huán)，(i=3,j=1,next[3]=1)依次往下循環(huán)

else

j=next[j];

}

}//這段代碼的目的就是為了計(jì)算出當(dāng)前要匹配的串T的next數(shù)組

int Index_KMP(char* S,char* T,int pos)

{

int i=pos;

int j=1;

int next[255];

get_next(T,next);

while(i<=strlen(S)&&j<=strlen(T))

{

if(j==0||S[i-1]==T[j-1])

{

++i;

++j;

}

else

j=next[j];//起到回溯的作用

}

if(j>strlen(T))

return (i-strlen(T)-1);

else

return 0;

}

int main()

{

　　char* T="bc";

　　 char* S="babaacbababcbababcbcbc";

　　 int pos=1;

　　int next[255];

　　get_next(T,next);

　　for(int j=1;j<=2;j++)

　　 cout<<"j="<<j<<":"<<"next"<<"["<<j<<"]"<<next[j]<<endl;

　　cout<<"子串T在主串S第"<<pos<<"個(gè)字符之后的第"<<Index_KMP(S,T,pos)<<"個(gè)位置"<<endl;

　　 return 0;

}