模式匹配的kmp算法(已修改)
2025-08-29 13:40 本頁(yè)面
【正文】 模式匹配的kmp算法Kmp算法是由Knuth、Morris、Pratt與1969年夏天提出的快速串匹配算法，它是由對(duì)BF算法的很大改進(jìn)而成的，這主要體現(xiàn)在每當(dāng)某趟匹配失敗是，指針不必回溯，而是利用已經(jīng)得到的“部分匹配”結(jié)果，將模式向右“滑動(dòng)“若干個(gè)位置后繼續(xù)比較。由于KMP算法避免了BF算法中頻繁的回溯，普遍提高了模式匹配的工作效率，因此它又被稱(chēng)為“不回溯的字符串搜索算法”。假設(shè)有目標(biāo)串T(t0,t1,t2,t3……,tm1)和模式串P(p０,p1,p2,p3,…pn1),使用BF算法進(jìn)行模式匹配，當(dāng)進(jìn)行第一輪比較時(shí)，若tk≠pk，則算法結(jié)束本輪比較，如下所示： T t0,t1,t2,…tk,tk+1,…tn2,tn1,…tm2,tm1 P p0,p1,p2,…pk,pk+1…,pn2,pn1 （第一輪比較結(jié)束）由于在字符串Ｔ與Ｐ中第一個(gè)不相等的字符位于ｋ處，所以?xún)勺址埃雮€(gè)字符是相等的。此時(shí)，可用字符串P(p0,p1,p2,p3,…pk1) 字符串T(t0,t1,t2,t3……,tk1)，于是原目標(biāo)串可轉(zhuǎn)化為T(mén)(p0,p1,p2,p3,…pk1，pk……,tm1)。在進(jìn)行第二輪比較前，算法同樣把字符串P整體向后移動(dòng)一個(gè)字符，此時(shí)字符串T與P之間的關(guān)系如下： T p0,p1,p2,…pk1,pk, …tn2,tn1,…tm2,tm1 P p0,p1,p2,…pk,pk+1…,pn2,pn1(第二輪比較)在第二輪比較中算法首先要比較的字符是P中首字符
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1