KMP算法的詳細解釋及實現

這是我自己學習算法時有關KMP的學習筆記，代碼注釋的十分的詳細，分享給大家，希望對大家有所幫助 在介紹KMP算法之前，

先來介紹一下樸素模式匹配算法：

樸素模式匹配算法：

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

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

2，然后從主串的第二位開始，會發現主串的第二位字母與T的第一位字母不同，所以匹配失敗，然后再從主串的第三位開始，

3，經過這樣的依次嘗試后，之到主串的第五位開始，S與T的6個字母完全匹配成功

該樸素模式匹配算法的代碼實現是：

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

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

{

int i=pos-1;//i用于主串S中當前位置的下標,S[0]是主串T的第一個字符

int j=0;//j用于子串T中當前位置下標值，即T[0]是字串T的第一個字符

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

{

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

{

++i;

++j;

}

else

{

i=i-j+1;//eg:如果第一次匹配時，不相等則使i=i-j+2=i+1;即向下走一個字母，以i=0為例，剛開始從主串第一個位置開始，如果S[i]==T[j]一直滿足，則i和j同步變化，即i=j;一旦有不相等的字母時，i=i-j+1,實際就是i=1；然后再從主串的第二個字母開始

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

}

}

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

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

else

return 0;

}

KMP模式匹配算法

KMP算法中把T串各個位置的j值的變化定義為一個數組next，那么next的長度就是T串的長度；

next數組值得推導：

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

1,當j=1時，next[1]=0;

2,當j=2時，j由1到j-1只有字符"a",next[2]=1;

3,當j=3時，j由1到j-1就只有字符串"ab"，顯然"a"與"b"不相等，所以next[3]=1;

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

T="ababaaaba";

1,當j=1時，next[1]=0;

2,當j=2時，next[2]=1;

3,當j=3時，next[3]=1;

4,當j=4時，next[4]=2;//j由1到j-1的串是"aba",前綴字符"a"與后綴字符"a"相等，next[4]=2;

5,當j=5時，next[5]=3;//串是"abab",前綴是"ab",后綴是"ab",有兩個相同的字符，所以為3

6,當j=6時，next[6]=4;//串是"ababa",前綴是"aba"，后綴是"aba",有三個相同的字符，所以為4

7,當j=7時，next[7]=2;//串是"ababaa",前綴字符是"a"與后綴字符"a"相等，有兩個相同的字符，所以為2

8,當j=8時，next[8]=2;//串是"ababaaa",前綴字符是"a"與后綴字符"a"相等，有兩個相同的字符，所以為2

9,當j=9時，next[9]=3;//串是"ababaaab",前綴字符是"ab",后綴字符也為"ab",有兩個相同的字符，所以為3

10,當j=10時，next[10]=4;//串是"ababaaaba",前綴字符是"aba",后綴字符也為"aba",有三個相同的字符，所以為4

KMP模式匹配算法實現

1，通過計算返回子串T的next數組

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"為例：該循環的執行順序:第一步,j=0,執行,（i=2,j=1,next[2]=1）第二步，不符合循環條件，j=next[1]=0,j又變為0為了再次進入循環，(i=3,j=1,next[3]=1)依次往下循環

else

j=next[j];

}

}

//這段代碼的目的就是為了計算出當前要匹配的串T的next數組

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;

}

附加一個實例：

#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"為例：該循環的執行順序:第一步,j=0,執行,（i=2,j=1,next[2]=1）第二步，不符合循環條件，j=next[1]=0,j又變為0為了再次進入循環，(i=3,j=1,next[3]=1)依次往下循環

else

j=next[j];

}

}//這段代碼的目的就是為了計算出當前要匹配的串T的next數組

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<<"個字符之后的第"<<Index_KMP(S,T,pos)<<"個位置"<<endl;

　　 return 0;

}