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


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

讓我們先來看個(gè)例題:

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:? 樸素的模式匹配算法(思路簡單,但不夠簡便時(shí)間長 有回溯) : 最簡單和最直接的做法.用P中的字符依次與T中的字符進(jìn)行比較 遇到不相等的字符,則可將P右移一個(gè)字符,從新進(jìn)行比較,直到某次匹配成功或者到達(dá)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????????????

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


3.KMP算法解決匹配中哪些主要問題:?
A.當(dāng)字符串比較出現(xiàn)不等時(shí),確定下一趟比較前 應(yīng)該將P右移多少個(gè)字符;?
B. P右移后,應(yīng)該從哪個(gè)字符開始和T中剛才比較時(shí)不等的那個(gè)字符繼續(xù)開始比較.

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

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

?C.next的計(jì)算:? 以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數(shù)組(關(guān)于修正我會(huì)在下次提到).
如1:我們要算next[2]的值,有關(guān)的為P本身的前2個(gè)字符0,1.?? 在字符串01中,尋找出?? "左右相同的最大字符串,此字符串所含字符的個(gè)數(shù)就為next[i]的值"而0不等于1,相同字符串不存在,所以next[i] = 0;

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

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


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

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

?????????????
???????????? 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;
}


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