KMP算法
八月 5, 2012 at 7:00 下午
—
Easton
查找算法实例
让我们用一个实例来演示这个算法。在任意给定时间，本算法被两个整数 m 和 i 所决定： m 代表主文字符串S 内匹配字符串 W 的当前查找位置；i 代表匹配字符串W当前做比较的字符位置。图示如下：
m: 01234567890123456789012
S: ABC ABCDAB ABCDABCDABDE
W: ABCDABD
i: 0123456
我們從 W 與 S 的開頭比較起。我們比對到 S[3](=' ') 時，發現 W[3](='D') 與其不符。接著並不是從S[1]比較下去。我們已經知道 S[1]~S[3]不與 W[0] 相合。因此，略過這些字元，令 m = 4 以及 i = 0。
m: 01234567890123456789012
S: ABC ABCDAB ABCDABCDABDE
W: ABCDABD
i: 0123456
如上所示，我們檢核了 "ABCDAB" 這個字串。然而，這與目標仍有些差異。我們可以注意到，"AB"在字串頭尾處出現了兩次。這意味著尾端的"AB" 可以作為下次比較的起始點。因此，我們令 m = 8, i = 2，繼續比較。圖示如下：
m: 01234567890123456789012
S: ABC ABCDAB ABCDABCDABDE
W: ABCDABD
i: 0123456
於 m = 10, i = 2 的地方，又出現不相符的情況。類似地，令 m = 11, i = 0 繼續比較：
m: 01234567890123456789012
S: ABC ABCDAB ABCDABCDABDE
W: ABCDABD
i: 0123456
這時，S[17](='C') 不與 W[6]相同，但是亦出現了兩次 "AB"，我們採取一貫的作法，令 m = 15 和 i = 2 ，繼續搜尋。
m: 01234567890123456789012
S: ABC ABCDAB ABCDABCDABDE
W: ABCDABD
i: 0123456
我們找到完全匹配的字串了，其起始位置於 S[15] 的地方。
471a0042-e6ba-4cdb-a99b-5fb47bf3d18a|1|3.0|96d5b379-7e1d-4dac-a6ba-1e50db561b04
Posted in: 技术文章
Tags: KMP算法