KMP 算法是計(jì)算機(jī)字符串匹配的常規(guī)算法效扫。wiki
本篇文章借助簡(jiǎn)單示例，用通俗易懂的方式描述對(duì) KMP 算法的理解莉恼。
匹配值表
對(duì)于 KMP 來(lái)說(shuō)咕村，“匹配值表”是很關(guān)鍵的。下面我們從簡(jiǎn)單示例出發(fā)描述匹配值表是如何產(chǎn)生的来吩，以便理解敢辩。
現(xiàn)在 我們需要查找的字符串是 “ABABABCA”蔽莱。
在描述“匹配值表“之前，我們需要簡(jiǎn)短的介紹下前綴和后綴的概念:
前綴：從 0 位戚长，依次截取 1 到(len - 1)長(zhǎng)度字符串的集合
后綴：從 len - 1 位反序盗冷，依次截取 1 到(len - 1)長(zhǎng)度字符串的集合
| 字符串 | 前綴集合 | 后綴集合 | 前綴后綴交集 |
|---|---|---|---|
| "A" | [] | [] | [] |
| "AB" | [A] | [B] | [] |
| "ABA" | [A,AB] | [A, BA] | [A] |
| "ABAB" | [A, AB, ABA] | [B, AB, BAB] | [AB] |
| "ABABA" | [A, AB, ABA, ABAB] | [A, BA, ABA, BABA] | [A, ABA] |
| "ABABAB" | [A, AB, ABA, ABAB, ABABA] | [B, AB, BAB, ABAB, BABAB] | [AB, ABAB] |
| "ABABABC" | [A, AB, ABA, ABAB, ABABA, ABABAB] | [C, BC, ABC, BABC, ABABC, BABABC] | [] |
| "ABABABCA" | [A, AB, ABA, ABAB, ABABA, ABABAB, ABABABC] | [A, CA, BCA, ABCA, BABCA, ABABCA, BABABCA] | [A] |
從上表，如果耐心看同廉，完全可以理解前綴和后綴的概念仪糖。
那么“匹配值”又是指什么呢？
“匹配值”是指前綴和后綴集合迫肖，最長(zhǎng)共有元素的長(zhǎng)度锅劝，即交集中最長(zhǎng)元素的長(zhǎng)度
那么不難從上表中得出每一位(index)字符對(duì)應(yīng)“匹配值(value)”:
char: | A | B | A | B | A | B | C | A |
index:| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
value:| 0 | 0 | 1 | 2 | 3 | 4 | 0 | 1 |
匹配值表的使用
我們可以根據(jù)匹配值表來(lái)加速查找匹配的過(guò)程。
下面還是舉例說(shuō)明問(wèn)題：
在字符串"BACBABABAABCBABABABCA"(text)中查找上文中的字符串"ABABABCA"(pattern)蟆湖，
下文中對(duì)兩個(gè)字符串的代稱為括號(hào)之內(nèi)的單詞故爵。
從 text 第一位開(kāi)始匹配，第一次匹配成功是這樣：
BACBABABAABCBABABABCA
|
ABABABCA
那么開(kāi)始往后匹配隅津，發(fā)現(xiàn) text 的第二位"C"和 pattern 的第二位"B"不匹配诬垂，
所以當(dāng)前部分匹配長(zhǎng)度為1(只有一個(gè)A)，并且根據(jù)上文的匹配值表得到伦仍，當(dāng)前的匹配值為 0结窘。
移動(dòng)位數(shù) = 已匹配字符長(zhǎng)度 - 對(duì)應(yīng)位的匹配值
即 移動(dòng)位數(shù) = 1 - 0，所以我們繼續(xù)向后移一位進(jìn)行匹配呢铆。
再一次匹配成功的情形：
BACBABABAABCBABABABCA
|||||
ABABABCA
此時(shí)晦鞋，text 中的"A"與 pattern 中的 "B" 不匹配，如果不按照算法棺克，肯定是繼續(xù)后移一位進(jìn)行匹配悠垛。
如果根據(jù)上述計(jì)算公式：
移動(dòng)位數(shù) = "ABABA".length - pattern[4]的匹配值
即 5 - 3 = 2
所以我們可以一次后移兩位：
BACBABABAABCBABABABCA
xx|||
ABABABCA
又不匹配了，此時(shí)應(yīng)該后移
"ABA".length - pattern[2]的匹配值
即 3 - 1 = 2
繼續(xù)后移兩位：
BACBABABAABCBABABABCA
xx|
ABABABCA
繼續(xù)后移
"A".length - pattern[0]的匹配值
即 1 - 0 = 1
后移一位：
BACBABABAABCBABABABCA
x||
ABABABCA
繼續(xù)后移
"AB".length - pattern[1]的匹配值
即 2 - 0 = 2
后移兩位：
BACBABABAABCBABABABCA
xx|
ABABABCA
第一位都不匹配娜谊，我們繼續(xù)往后移動(dòng)直到匹配成功
BACBABABAABCBABABABCA
||||||||
ABABABCA
移動(dòng)幾次之后(step=1)确买，找到了最終匹配結(jié)果。
參考：
http://jakeboxer.com/blog/2009/12/13/the-knuth-morris-pratt-algorithm-in-my-own-words/
