???????????? KMP 匹配算法是由 "Knuth? Morris? Pratt"? 提出的一種快速的模式匹配算法. (串)


1.待解決的問題: 假設P為給定的子串,T是待查找的字符串,要求從T中找出與P相同的所有子串,這稱為模式匹配問題. (可以給出子串在T中的位置) (下文中提到的P和T分別為子串和目標串)

讓我們先來看個例題:

T:???t₀??????t₁?????t₂??????t₃?.... t_m-1 ... t_n-1

P:???p₀????? p₁???? p₂??????p₃ .....p_m-1??????????
???????????????????????????????????????????????

從T的最左邊開始比較,使得 T_K = P_K? , 則匹配成功

2.解決模式匹配問題的方案:

A:? 樸素的模式匹配算法(思路簡單,但不夠簡便時間長 有回溯) : 最簡單和最直接的做法.用P中的字符依次與T中的字符進行比較 遇到不相等的字符,則可將P右移一個字符,從新進行比較,直到某次匹配成功或者到達P的最右字符移出T為止.

如: 若P="aaaba", T="aaabbaaaba", 則匹配過程如下圖

?T:???? a???a???a???b???b???a???a???a?? b? a
?P:?????a???a???a???b???a?????????????????????????????????????????????????????????????????
????????????a???a???a???b???a?????????????????
??????????????????????????????? .....
??????????????????????????? a???a???a???b? a????????????

從上不難分析,最壞的情況是"每次比較都在最后一個字符出現不等,每趟最多比較M次,最多比較N-M+1趟,總的比較次數最多為M*(N-M+1)" ,時間復雜性為0(M*N).?在P右移一位時,不管上一趟比較的中間結果是什么,因此回溯是不可避免的(如: 前3個aaa 不需要一位一位的移?)?.下面我來介紹無回溯的KMP算法.


3.KMP算法解決匹配中哪些主要問題:?
A.當字符串比較出現不等時,確定下一趟比較前 應該將P右移多少個字符;?
B. P右移后,應該從哪個字符開始和T中剛才比較時不等的那個字符繼續開始比較.

??? 我們通過樸素模式匹配的例子來引出問題. 在第一次比較過程中失敗的是P的第4個字符b,這表明P的前4個字符是成功的.模式P的第3個字符b在它的前3個字符(aaa)中并未出現.因此,在下一次比較時候,至少要將P向后移4個字符; 再看P的第一個字符與最后一個字符是相同的因此將P右移4個字符后 再從第一個字符比較 可定也是不等的.? 綜上所訴:應該將P右移5個字符 再從P的第0個字符和T的第5個字符開始比較!

KMP算法核心: KMP算法借助于一個輔助數組next來確定當匹配過程中出現不等時,模式P右移的位置和開始比較的位置.next[i]的取值只與模式P本身的前i+1項有關,而與目標T無關.???? 匹配過程中遇到Pi不等于Tj時,若next[i]>=0,則應將P右移i-next[i]位個字符,用P中的第next[i]個字符與Tj 進行比較;若:next[i]= -1,P中的任何字符都不必再與Tj比較,而應將P右移i+1個字符,從P0和Tj+1從新開始下一輪比較(可能不太好理解,自己找個例子,對著話一句一句試試看)
?
? 因此只要計算出與模式P相關的next數組,按上面的含義,就可以很容易地給出串的匹配算法.(問題就這樣轉化了)

?C.next的計算:? 以P = " 01001010100001"為例.

??i???:????????????0?? 1???2?? 3???4???5???6????.....??
? P?? :????????????0???1???0???0???1???0?? 1????.....

?j(next[i]) :?????-1???0???0?? 1?? 1?? 2???3????.....
修正(next[i])??:? -1???0??-1???1???0??-1???3????.....
例子中的j(next[i])為未修正前的next數組(關于修正我會在下次提到).
如1:我們要算next[2]的值,有關的為P本身的前2個字符0,1.?? 在字符串01中,尋找出?? "左右相同的最大字符串,此字符串所含字符的個數就為next[i]的值"而0不等于1,相同字符串不存在,所以next[i] = 0;

如2:我們要算next[6]的值,有關的為P本身前6個字符010010? 此字符串中010 = 010
左右相同的最大字符串為010,個數為3.所以next[i]=3;

如3:我們要算next[5]的值,有關的為P本身前5個字符01001 此字符串中 01=01 左右相同的最大字符串為01,個數為2.所以next[i]=2;


通過上面的例子大家應該有所了解了,有什么問題可以留言給我.

???????????????????????

?????????????
???????????? KMP的算法???? VC++6.0

?

Cmystring::GenKMPNext(int *next, CMyString *s)

{ int i=0; j=-1;

?? next[0]=-1;

?while(i<s->length)

? {

? while(j>=0&&s->str[i]!=s->str[j])

???? j=next[j];

?? i++;j++;

?? if(s->str[i]==s->str[j])

????? next[i]=next[j];
? else? next[i]=j;}

}


/////////////////// 串類的find()方法 KMP匹配算法////////////////////////
int CMyString::find(const CMyString *S)
{
??? int i , j , *next = new int[s->length];
??? GenKMPNext(next, s);
????for(i=?0,j=0;i< s->length&&j<length;)
????{
????????if( s->str[i] = =str[j] ) { i++ , j++;}
??????? else
??????????? if(next[i] >=0)
?????????????????i =?next[i];
????????????else
??????????? { i = 0; j++}
?????}
???? if(i>= s->length)
?????? return? j - s->length;
???? else
????????? return -1;
}


????????????????