? ? ? ? 早上起來刷微信，看到前同事分享了一個(gè)搜索算法的科普文章，一看遍入迷，叫做kmp算法。kmp算法可以百度一下，挺多講的，我這里記錄一下我在學(xué)習(xí)理解過程中的一些小發(fā)現(xiàn)，有助于簡(jiǎn)化對(duì)于該算法的程序?qū)崿F(xiàn)過程，或者說是對(duì)理解該算法核心精髓的幫助。

? ? ? ? kmp的核心精髓是那個(gè)匹配表的計(jì)算

? ? ? ? 原計(jì)算方式如下兩個(gè)圖：

? ? ? ? kmp匹配表官方計(jì)算方式：

? ? ? ? 官方這種方式，匹配表比較簡(jiǎn)單，但是需要根據(jù)匹配失敗的前綴情況對(duì)位置來查找獲取匹配值。我這里想出了一個(gè)簡(jiǎn)化版的匹配表，簡(jiǎn)單來講就是ABCABD這個(gè)字符串，匹配失敗的情況下，有這么幾種前綴是可能匹配成功的，都列出來：

A? ?AB? ?ABC? ?ABCA? ?ABCAB

? ? ????用kmp的前后綴思路計(jì)算每種情況的匹配值，結(jié)果：

A? ? ? ? ? ? ? ? ? ? ? ?沒有相同，長(zhǎng)度0，得出匹配值0

AB? ? ? ? ? ? ? ? ? ? 沒有相同，長(zhǎng)度0，得出匹配值0

ABC? ? ? ? ? ? ? ? ?沒有相同，長(zhǎng)度0，得出匹配值0

ABCA? ? ? ? ? ? ? ? 相同的為A，長(zhǎng)度1，得出匹配值1

ABCAB? ? ? ? ? ? ?相同的為AB，長(zhǎng)度2，得出匹配值2

????? ? 把上表保存到一個(gè)map中，key為前綴，值為匹配值。計(jì)算過程中，用匹配失敗出現(xiàn)的情況對(duì)應(yīng)的前綴類型，直接到這個(gè)map中找對(duì)應(yīng)的匹配值即可，然后用前綴字符串長(zhǎng)度減去匹配值即可獲取下次的偏移量（和kmp算法后續(xù)算偏移量的方法一樣）。這樣程序?qū)崿F(xiàn)起來會(huì)邏輯會(huì)簡(jiǎn)單明了一些，畢竟我認(rèn)為不影響多少時(shí)效性的情況下，代碼邏輯越簡(jiǎn)單越好。

? ? ? ? 其實(shí)kmp算法的核心思想就是考慮：匹配失敗的情況下，成功的前綴部分中是否有重復(fù)內(nèi)容，從而判斷下次檢索需要前進(jìn)多少位，而不需要一位一位的檢索，避免了一些無意義的動(dòng)作，從而提升檢索效率。