聯系我們 - 廣告服務 - 聯系電話：
您的當前位置： > 關注 > > 正文

如何理解KMT字符串匹配算法？如何計算出KMT數組？

來源：CSDN 時間：2023-03-02 09:43:44

KMT字符串匹配算法的核心是1. 如何計算出NEXT數組 2. 對該算法思想的理解。今天又復習了下這個算法，領悟了一套自認為更形象的理解。概括一句話就是：可以把KMT看成是暴力算法的加速版本或者跳躍版本，而如何加速跳躍則是NEXT數組的用途所在。


【資料圖】

首先考慮暴力算法，T(目標串），P是模式串，即尋找P在T中的位置。

T: AACAAXEE

P: AACAAZDD

在X與Z處，出現了不匹配。按照暴力算法，我們會把P按步長1逐步的從T往后移，也就是第二次從T的B位置，第三次是C位置開始，以此類推。

KMT算法相比上面方法的改進之處就是，這個步長不用一直為1. 比如XZ不匹配的時候，可以直接步長3來進行第二步的匹配。也就是說P在當前不匹配的位置左邊，即

T: AACAA

P:AACAA    尋找這兩個最大的重疊部分（沒移動前當然是最大的，但是這個時候已經發現XZ不匹配，所以我們要排除這個?？梢园裈跟P看出寫著AACAA的并列的兩張紙條，P往右慢慢移動，尋找最大的兩張紙條重疊部分即可。）這樣可以避免無意義的一步步的走，比如要是只走一步，

AACAA

AACAA， 如果我們已經知道這個不是最大重疊串，那么也就是說這一步走完后，T跟P肯定不等（因為目前重疊的部分已經不等了），所以我們要尋找最大重疊串。

T：AACAAXEE

P：      AACAAZDD

以T為參照就是T的當前下標不變，P移動到合適的下標位置。 緊接著，發現XC不等，于是在C左邊尋找最大的跳躍步長。

責任編輯：

標簽：

相關推薦：

精彩放送：

新聞聚焦
Top 岛国精品在线