字符串的形式婚配詳解--BF算法與KMP算法。本站提示廣大學習愛好者：（字符串的形式婚配詳解--BF算法與KMP算法）文章只能為提供參考，不一定能成為您想要的結果。以下是字符串的形式婚配詳解--BF算法與KMP算法正文
一.BF算法
BF算法是通俗的形式婚配算法，BF算法的思惟就是將目的串S的第一個字符與形式串P的第一個字符停止婚配，若相等，則持續比擬S的第二個字符和P的第二個字符；若不相等，則比擬S的第二個字符和P的第一個字符，順次比擬下去，直到得出最初的婚配成果。
舉例解釋：
S: ababcababa
P: ababa
BF算法婚配的步調以下
i=0 i=1 i=2 i=3 i=4
第一趟:ababcababa 第二趟:ababcababa 第三趟:ababcababa 第四趟:ababcababa 第五趟:ababcababa
ababa ababa ababa ababa ababa
j=0 j=1 j=2 j=3 j=4(i和j回溯)
i=1 i=2 i=3 i=4 i=3
第六趟:ababcababa 第七趟:ababcababa 第八趟:ababcababa 第九趟:ababcababa 第十趟:ababcababa
ababa ababa ababa ababa ababa
j=0 j=0 j=1 j=2(i和j回溯) j=0
i=4 i=5 i=6 i=7 i=8
第十一趟:ababcababa 第十二趟:ababcababa 第十三趟:ababcababa 第十四趟:ababcababa 第十五趟:ababcababa
ababa ababa ababa ababa ababa
j=0 j=0 j=1 j=2 j=3
i=9
第十六趟:ababcababa
ababa
j=4(婚配勝利)
代碼完成:
int BFMatch(char *s,char *p)
{
int i,j;
i=0;
while(i<strlen(s))
{
j=0;
while(s[i]==p[j]&&j<strlen(p))
{
i++;
j++;
}
if(j==strlen(p))
return i-strlen(p);
i=i-j+1; //指針i回溯
}
return -1;
}
其其實下面的婚配進程中，有許多比擬是過剩的。在第五趟婚配掉敗的時刻，在第六趟，i可以堅持不變，j值為2。由於在後面婚配的進程中，關於串S，已知s0s1s2s3=p0p1p2p3，又由於p0!=p1!，所以第六趟的婚配是過剩的。又因為p0==p2,p1==p3，所以第七趟和第八趟的婚配也是過剩的。在KMP算法中就省略了這些過剩的婚配。
二.KMP算法
KMP算法之所以叫做KMP算法是由於這個算法是由三小我配合提出來的，就取三小我名字的首字母作為該算法的名字。其實KMP算法與BF算法的差別就在於KMP算法奇妙的清除了指針i的回溯成績，只需肯定下次婚配j的地位便可，使得成績的龐雜度由O(mn)降低到O(m+n)。
在KMP算法中，為了肯定在婚配不勝利時，下次婚配時j的地位，引入了next[]數組，next[j]的值表現P[0...j-1]中最長後綴的長度等於雷同字符序列的前綴。
關於next[]數組的界說以下：
1) next[j] = -1 j = 0
2) next[j] = max(k): 0<k<j P[0...k-1]=P[j-k,j-1]
3) next[j] = 0 其他
如：
P a b a b a
j 0 1 2 3 4
next -1 0 0 1 2
即next[j]=k>0時，表現P[0...k-1]=P[j-k,j-1]
是以KMP算法的思惟就是：在婚配進程稱，若產生不婚配的情形，假如next[j]>=0，則目的串的指針i不變，將形式串的指針j挪動到next[j]的地位持續停止婚配；若next[j]=-1，則將i右移1位，並將j置0，持續停止比擬。
代碼完成以下：
int KMPMatch(char *s,char *p)
{
int next[100];
int i,j;
i=0;
j=0;
getNext(p,next);
while(i<strlen(s))
{
if(j==-1||s[i]==p[j])
{
i++;
j++;
}
else
{
j=next[j]; //清除了指針i的回溯
}
if(j==strlen(p))
return i-strlen(p);
}
return -1;
}
是以KMP算法的症結在於求算next[]數組的值，即求算形式串每一個地位處的最長後綴與前綴雷同的長度， 而求算next[]數組的值有兩種思緒，第一種思緒是用遞推的思惟去求算，還有一種就是直接去求解。
1.依照遞推的思惟：
依據界說next[0]=-1，假定next[j]=k, 即P[0...k-1]==P[j-k,j-1]
1)若P[j]==P[k]，則有P[0..k]==P[j-k,j]，很明顯，next[j+1]=next[j]+1=k+1;
2)若P[j]!=P[k]，則可以把其看作形式婚配的成績，即婚配掉敗的時刻，k值若何挪動，明顯k=next[k]。
是以可以如許去完成：
void getNext(char *p,int *next)
{
int j,k;
next[0]=-1;
j=0;
k=-1;
while(j<strlen(p)-1)
{
if(k==-1||p[j]==p[k]) //婚配的情形下,p[j]==p[k]
{
j++;
k++;
next[j]=k;
}
else //p[j]!=p[k]
k=next[k];
}
}
2.直接求解辦法
void getNext(char *p,int *next)
{
int i,j,temp;
for(i=0;i<strlen(p);i++)
{
if(i==0)
{
next[i]=-1; //next[0]=-1
}
else if(i==1)
{
next[i]=0; //next[1]=0
}
else
{
temp=i-1;
for(j=temp;j>0;j--)
{
if(equals(p,i,j))
{
next[i]=j; //找到最年夜的k值
break;
}
}
if(j==0)
next[i]=0;
}
}
}
bool equals(char *p,int i,int j) //斷定p[0...j-1]與p[i-j...i-1]能否相等
{
int k=0;
int s=i-j;
for(;k<=j-1&&s<=i-1;k++,s++)
{
if(p[k]!=p[s])
return false;
}
return true;
}
