模式匹配的kmp算法-全文預覽
【正文】 k, …tn2,tn1,…tm2,tm1 P p0,p1,p2,…pk,pk+1…,pn2,pn1(第二輪比較)在第二輪比較中算法首先要比較的字符是P中首字符p0與T中第二個字符p1，若p0與p1相等，則算法順序比較P中第二個字符p1與T中第三個字符p2；若不等，則算法仍然把模式串P整體向后移動一個字符，此時字符串T與P之間的關(guān)系如下 T p0,p1,p2,…pk1,pk, …tn2,tn1,…tm2,tm1P p0,…pk3,pk2,…,pn1（第三次比較）算法依照同樣的次序，首先對P中字符p0與T中字符p2進行比較，若相等，則順序比較后續(xù)的字母；若不等，則把字符串P整體向后移動一個字符。模式匹配的kmp算法Kmp算法是由Knuth、Morris、Pratt與1969年夏天提出的快速串匹配算法，它是由對BF算法的很大改進而成的，這主要體現(xiàn)在每當某趟匹配失敗是，指針不必回溯，而是利用已經(jīng)得到的“部分匹配”結(jié)果，將模式向右“滑動“若干個位置后繼續(xù)比較。此時，可用字符串P(p0,p1,p2,p3,…pk1) 字符串T(t0,t1,t2,t3……,tk1)，于是原目標串可轉(zhuǎn)化為T(p0,p1,p2,p3,…pk1，pk……,tm1)。而p0,p1,p2,p3全部是字符串P中的字符，它們之間的關(guān)系可以在調(diào)用字符串匹配算法前就確定下來。 接著是獲取失效函數(shù)值域的辦法，失效函數(shù)的取值k定義如下 K{k|0=kj}其中，k是滿足條件p0p1…pk=pjkpjk+1…pj的最大正整數(shù)。由于p0≠p2且p0
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1