一、前言
??在計算機科學中，Knuth-Morris-Pratt字串查找演算法（簡稱為KMP演算法）可在一個主文本字串S內查找一個詞W的出現位置，此演算法通過運用對這個詞在不匹配時本身就包含足夠的資訊來確定下一個匹配將在哪里開始的發現，從而避免重新檢查先前匹配的字符，這個演算法是由高德納和沃恩·普拉特在1974年構思，同年詹姆斯·H·莫里斯也獨立地設計出該演算法，最終由三人于1977年聯合發表，(from:wikipedia)
??KMP搜索(Knuth–Morris–Pratt string-searching)是字串匹配演算法中較為高效的演算法，它彌補了暴力匹配演算法的一些缺點，通過回溯避免了在字串匹配時不必要的步驟，縮短了匹配時間，它的時間復雜度只有O(m+n)，適合在有時間要求的情況下使用，同時也是某些比賽的考點，還是比較有用，但此方法本質上是AC自動機的一種特殊情況，存在一定的理解難度，本文只講解如何理解和實作kmp演算法，有關數學上的說明可以參考《演算法導論》字串匹配相關章節，
二、代碼
以下為實作代碼，可先瀏覽，之后再做分析，
#include <stdio.h>
#include <string.h>
void getnext(char *t); //計算子串的狀態轉移陣列的函式
int kmp(char *s,char *t); //kmp演算法的主要匹配搜索函式
int next[255]; //全域next陣列更方便呼叫，大小根據實際情況更改
int main(void)
{
int n;
char s[255],t[255];
printf("母串：");
scanf("%s",s);
printf("子串：");
scanf("%s",t);
n=kmp(s,t);
if(n==0)
printf("匹配失敗\n");
else
printf("在第%d位匹配成功",n);
return 0;
}
void getnext(char *t)
{
int i=0,j=-1,l=strlen(t); //j初始化為-1只是方便計算，更易于理解，無特殊含義，
next[0]=-1; //這里如果用next[i]=j后續有可能出現死回圈，故單獨賦值，
while(i<l)
{
if(j==-1||t[i]==t[j]) //t[i],t[j]分別表示前綴子串單個字符和后綴子串單個字符，若匹配成功則以一種累加
{ //的方式繼續向后匹配，所以每次比較一個字符，可以動手嘗試分步理解
++i,++j;
if(t[i]!=t[j]) //這里是針對原先方法的一些優化，后續會將
next[i]=j;
else
next[i]=next[j];
}
else
j=next[j]; //字符不相同時進行回溯
}
}
int kmp(char *s,char *t)
{
int i=0,j=0;
int sl=strlen(s),tl=strlen(t);
getnext(t);
while(i<sl&&j<tl)
{
if(j==-1||s[i]==t[j])
++i,++j;
else
j=next[j]; //字串失配時回溯到正確位置再次匹配
}
if(j==tl)
return i-tl+1;
else
return 0;
}
三、具體分析
1.求轉移陣列next的方法與分析
現在有母串s和子串t
s="abcdefgab"
t="abcdex"，
我們可以看出，兩個串前五位字符分別對應相等，只在第六位失配，如果按照暴力匹配是需要依次匹配一遍，但我們通過觀察可以看出，子串中六個字母各不相同，s串的首字母和t串的首字母相同，那么就意味著子串t的首字符不可能與母串2-5之間的字符匹配成功，那么這時，暴力匹配中就有一些步驟是完全可以省略的，之后的字符同理可知都能直接跳過，由于就算我們知道了s[5]!=t[5]，t[0]!=t[5]，我們也無法確定t[0]一定不等于s[5]，所以需要保留它們兩個匹配的那一次，
t[i]==s[i] (i=0,1,2,3,4)
t[0]!=t[j] (j=1,2,3,4)
可以推出：t[0]!=s[j] (j=1,2,3,4)
通過以上的例子，我們可以看出kmp演算法具體是根據什么回溯的，我們也可以看出這樣的回溯方式比暴力匹配好在哪里，我們既然是拿子串去匹配母串，那么肯定是指向子串的數字的回溯，也就是說，串中每個對應的next值與母串無關，我們現在可以繼續驗證字符重復的情況，現在我們有子串t
t="abcabx"
我們首先需要了解兩個概念：“前綴”和“后綴”，“前綴”指除了最后一個字符之外，一個字串的全部頭部組合，“后綴”指除了第一個字符之外，一個字串的全部尾部組合，最大公共值就是“前綴”和“后綴”的最長的共有元素的長度，其次，next陣列的下標j指向第n位的時候，計算的是前n-1個字符所組成的字串的最大公共值，因為next陣列描述的是字串在第n位失配時的轉移狀況，故不考慮第n位，我們可以發現“ab”出現了重復，故x處對應next陣列的值為2，即為最大公共值，這也是設next[0]=-1帶來的好處，更容易理解，更形象，之后若在x處失配，我們可以把整體向后挪動使得挪動之后的第一個ab對應挪動之前第二個ab的位置，繼續從c開始往后匹配，
??繼續思考，我們會發現剛才的t串中含有兩個a，兩個b，其實這時如果用首位的值去取代后續相同的字符的next值，可以再避免之前求next陣列方法某些情況下的重復匹配的缺陷，這個缺陷在一些連續出現同一字母的串中會出現，原因就不展開講了，可以用之前的方法來分析串“aaaabcde”和“aaaaax”來得到結論，最后t串的next陣列如下圖，可以嘗試自己去求，
至此，我們就得到了子串的轉移陣列next，
2.kmp匹配函式的分析
kmp搜索函式就比較簡單了，難點主要在next函式的理解上，結合next陣列把子串與母串進行匹配就行了，如果匹配失敗回傳0，匹配成功則回傳匹配成功的位置，此外，這只是kmp最簡單的用法，可以根據需要對他的功能進行增加，例如求最小子串，求子串在母串的哪些地方出現等，
四、結尾
其實還有很多其它的字串匹配演算法，例如Sunday演算法等較為優秀的字串模式匹配演算法，且有些效率比kmp要高，但理解kmp演算法也能幫助我們更好的理解其它演算法，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/102314.html
標籤：其他
上一篇：PAT乙級1019
下一篇：更改默認路徑安裝，迷茫了