KMP的由來(lái)
在KMP算法之前,對(duì)文本進(jìn)行匹配時(shí)使用的是樸素模式匹配算法,也就是最簡(jiǎn)單匹配算法.
當(dāng)然運(yùn)行效率也是讓人深惡痛絕,舉個(gè)例子:
現(xiàn)有長(zhǎng)度為n的模式串00001,和長(zhǎng)度為m的文本串0000000000000000000000000000000001.
按照樸素匹配算法最終時(shí)間復(fù)雜度為o{(m-n+1)*n}
這種有多個(gè)0和1重復(fù)字符的字符串,匹配模式卻仍需要挨個(gè)遍歷,這是十分糟糕的,所以最終KMP算法誕生了.
KMP和樸素算法的核心差別
樸素算法在匹配時(shí),子串和對(duì)比的目標(biāo)串都會(huì)不斷的進(jìn)行回溯對(duì)比,而KMP會(huì)先計(jì)算出子串的匹配數(shù)組,在進(jìn)行匹配時(shí)目標(biāo)串并不會(huì)進(jìn)行回溯,且子串回溯時(shí)會(huì)根據(jù)計(jì)算出的重復(fù)數(shù)組省略很多不必要的回溯.
下面就用例子進(jìn)行講解.
KMP的回溯原理
以下圖兩字符串匹配為例:
KMP核心是找出要匹配的子串的匹配值數(shù)組,如下圖給出的子串和匹配值.
"子串匹配值"就是"前綴"和"后綴"的最長(zhǎng)的共有元素的長(zhǎng)度脯燃。以"ABCDABD"為例萝风，
"A"的前綴和后綴都為空集，共有元素的長(zhǎng)度為0曙痘；
"AB"的前綴為[A]引几，后綴為[B]峰锁，共有元素的長(zhǎng)度為0步咪；
"ABC"的前綴為[A, AB]侣诺，后綴為[BC, C]，共有元素的長(zhǎng)度0挪拟；
"ABCD"的前綴為[A, AB, ABC]挨务，后綴為[BCD, CD, D]击你，共有元素的長(zhǎng)度為0玉组；
"ABCDA"的前綴為[A, AB, ABC, ABCD]谎柄，后綴為[BCDA, CDA, DA, A]，共有元素為"A"惯雳，長(zhǎng)度為1朝巫；
"ABCDAB"的前綴為[A, AB, ABC, ABCD, ABCDA]，后綴為[BCDAB, CDAB, DAB, AB, B]石景，共有元素為"AB"劈猿，長(zhǎng)度為2；
"ABCDABD"的前綴為[A, AB, ABC, ABCD, ABCDA, ABCDAB]潮孽，后綴為[BCDABD, CDABD, DABD, ABD, BD, D]揪荣，共有元素的長(zhǎng)度為0。
跳過(guò)前面一端不匹配的,我們直接來(lái)到匹配串生效的位置
已知空格與D不匹配時(shí)往史，前面六個(gè)字符"ABCDAB"是匹配的仗颈。查表可知，最后一個(gè)匹配字符B對(duì)應(yīng)的"部分匹配值"為2椎例，因此按照下面的公式算出向后移動(dòng)的位數(shù)：
移動(dòng)位數(shù) = 已匹配的字符數(shù) - 對(duì)應(yīng)的部分匹配值
因?yàn)?6 - 2 等于4挨决，所以將搜索詞向后移動(dòng)4位。
因?yàn)榭崭衽cＣ不匹配订歪，搜索詞還要繼續(xù)往后移脖祈。這時(shí)，已匹配的字符數(shù)為2（"AB"）刷晋，對(duì)應(yīng)的"部分匹配值"為0盖高。所以，移動(dòng)位數(shù) = 2 - 0眼虱，結(jié)果為 2或舞，于是將搜索詞向后移2位。
因?yàn)榭崭衽cA不匹配蒙幻，繼續(xù)后移一位映凳。
逐位比較，直到發(fā)現(xiàn)C與D不匹配邮破。于是诈豌，移動(dòng)位數(shù) = 6 - 2，繼續(xù)將搜索詞向后移動(dòng)4位抒和。
逐位比較矫渔，直到搜索詞的最后一位，發(fā)現(xiàn)完全匹配摧莽，于是搜索完成庙洼。如果還要繼續(xù)搜索（即找出全部匹配），移動(dòng)位數(shù) = 7 - 0，再將搜索詞向后移動(dòng)7位油够，這里就不再重復(fù)了蚁袭。
這么一看KMP是不是比樸素算法匹配次數(shù)少了很多?例子中也看出了KMP核心在于匹配數(shù)組,那如何通過(guò)代碼求出匹配數(shù)組呢?
KMP核心匹配串?dāng)?shù)組
下面是Java的偽代碼
public int[] get_next(char[] str) {
int i = 1;
int j = 0;
int[] next = new int[str.length];
next[0] = 0;
while (i < str.length) {
if (str[i]==(str[j])) { // 匹配記錄下當(dāng)前匹配的位置
++j;
next[i] = j; // 為了配合例子更便于理解,所以在++i之前便給匹配數(shù)組進(jìn)行了賦值
++i;
} else if (j == 0) { // 完全不匹配,跳至下一個(gè)字符
next[i] = j; // 同上理由
++j;
++i;
} else {
j = next[j - 1]; // 回溯至合適的位置
}
}
return next;
}
這段代碼中j = next[j - 1];是很多人懵逼的地方,當(dāng)然常規(guī)模式是j = next[j];.我這里配合例子進(jìn)行了改寫.
為什么不是遞減回溯,而是直接跳至數(shù)組中的匹配值,盡管從結(jié)果中可以看出這樣確實(shí)是高效的方式,但是為什么正好就是最合適呢?知其然不知其所以然.
下面按照上面思路來(lái)實(shí)現(xiàn)KMP算法就能知其所以然了.
KMP算法具體實(shí)現(xiàn)
// 求字符串t,在字符串s中的pos位之后首次出現(xiàn)的位置
public int index_KMP(char[] s, char[] t, int pos) {
int i = pos;
int j = 0;
int[] next = get_next(t);
while (i < s.length && j < t.length) {
if (s[i] == t[j]) {
i++;
j++;
} else if (j == 0) {
i++;
} else {
// j的回溯位置可以根據(jù)上面例子中的公式來(lái)套.
// 移動(dòng)位數(shù) = 已匹配的字符數(shù) - 對(duì)應(yīng)的部分匹配值;
// 已匹配的字符數(shù)為: j;
// 對(duì)應(yīng)部分匹配值為: next[j - 1];
// 移動(dòng)位數(shù)為: j - (next[j - 1]);
// 新的索引 = 舊索引 - 移動(dòng)位數(shù);
// j = j - (j - (next[j - 1]));
j = next[j - 1];
}
}
if (j == t.length) {
return i - t.length;
}
return 0;
}
從這里就可以看出為什么回溯的位置是j = next[j - 1],在于常規(guī)的對(duì)應(yīng)一下,常規(guī)的kmp算法數(shù)組中當(dāng)前位對(duì)應(yīng)的是前一位的重復(fù)值,并不是本身的重復(fù)值.
在上述公式中我們需要找到前一位的對(duì)應(yīng)值,來(lái)進(jìn)行位移操作,而常規(guī)KMP中前一位重復(fù)值就是next[j].
所以最終的回縮過(guò)程就是 j = next[j];
便于理解,在求自身匹配數(shù)組時(shí),也可以將不斷變換的尾串看做成子串,這樣就是子串和目標(biāo)串進(jìn)行匹配,就可以套用上面的公式得出j = next[j],只不過(guò)尾串一直在變化而已.
在改進(jìn)KMP算法時(shí),需先將算法恢復(fù)到正常模式(想了半天不知道在改進(jìn)模式的情況下如何繼續(xù)推導(dǎo)了...)
常規(guī)的KMP匹配數(shù)組獲取代碼如下:
// 由于數(shù)組的角標(biāo)是從0開(kāi)始的,所以的出來(lái)的結(jié)果和書上所說(shuō)的統(tǒng)統(tǒng)小一.
public int[] get_next(char[] str) {
int i = 0;
int j = -1;
int[] nextval = new int[str.length];
nextval[0] = -1;
while (i < str.length - 1) {
if (j == -1 || str[i] == (str[j])) { // 匹配記錄下當(dāng)前匹配的位置
++j;
++i;
nextval[i] = j;
} else {
j = nextval[j]; // 回溯至合適的位置
}
}
return nextval;
}
常規(guī)模式KMP匹配代碼如下:
public int index_KMP(char[] s, char[] t, int pos) {
int i = pos;
int j = 0;
int[] next = get_next(t);
while (i < s.length && j < t.length) {
if (j == 0 || s[i] == t[j]) {
i++;
j++;
} else {
j = next[j];
}
}
if (j == t.length) {
return i - t.length;
}
return 0;
}
KMP算法的改進(jìn)
引自July:從頭到尾徹底理解KMP（2014年8月22日版）
用前面的next 數(shù)組方法求模式串“abab”的next 數(shù)組，可得其next 數(shù)組為-1 0 0 1（0 0 1 2整體右移一位石咬，初值賦為-1）揩悄，當(dāng)它跟下圖中的文本串去匹配的時(shí)候，發(fā)現(xiàn)b跟c失配鬼悠，于是模式串右移j - next[j] = 3 - 1 =2位删性。
P表子串(abab),s表目標(biāo)串(abacabababc)
右移2位后，b又跟c失配焕窝。事實(shí)上蹬挺，因?yàn)樵谏弦徊降钠ヅ渲校呀?jīng)得知p[3] = b它掂，與s[3] = c失配汗侵，而右移兩位之后，讓p[next[3]] = p[1] = b 再跟s[3]匹配時(shí)群发，必然失配晰韵。問(wèn)題出在哪呢？
問(wèn)題出在不該出現(xiàn)p[j] = p[next[j]]熟妓。為什么呢雪猪？理由是：當(dāng)p[j] != s[i] 時(shí)，下次匹配必然是p[next[j]] 跟s[i]匹配起愈，如果p[j] = p[next[j]]只恨，必然導(dǎo)致后一步匹配失敗（因?yàn)閜[j]已經(jīng)跟s[i]失配抬虽，然后你還用跟p[j]等同的值p[next[j]]去跟s[i]匹配官觅，很顯然，必然失配）阐污，所以不能允許p[j] = p[next[j]]休涤。如果出現(xiàn)了p[j] = p[next[j] ]咋辦呢？如果出現(xiàn)了笛辟，則需要再次遞歸功氨，即令next[j] = next[next[j]]。
public int[] get_nextval(char[] str) {
int i = 0;
int j = -1;
int[] nextval = new int[str.length];
nextval[0] = -1;
while (i < str.length - 1) {
if (j == -1 || str[i] == (str[j])) { // 匹配記錄下當(dāng)前匹配的位置;
++j;
++i;
nextval[i] = j;
if (str[i] != str[j]) { // 當(dāng)前字符與前綴字符不同;
nextval[i] = j; // 當(dāng)前的j賦值給nextval[i];
} else {
nextval[i] = nextval[j]; // 與前綴字符相同,那么將前綴字符的nextval值付給在i位的值.
}
} else {
j = nextval[j]; // 回溯至合適的位置
}
}
return nextval;
}
本文到此結(jié)束.
前面KMP推導(dǎo)算是個(gè)人理解,后面的改進(jìn)照搬July的,因?yàn)閷?shí)在說(shuō)的很清楚了,沒(méi)有能補(bǔ)充的,若還是有點(diǎn)蒙圈,可以看July原文,或許更容易理解.
