KMP算法的来龙去脉
1. 引言
字符串匹配是極為常見的一種模式匹配。簡(jiǎn)單地說，就是判斷主串TT中是否出現(xiàn)該模式串PP，即PP為TT的子串。特別地，定義主串為T[0…n?1]T[0…n?1]，模式串為P[0…p?1]P[0…p?1]，則主串與模式串的長(zhǎng)度各為nn與pp。
暴力匹配
暴力匹配方法的思想非常樸素：
下圖給出了暴力匹配的例子，主串T="ababcabcacbab"，模式串P="abcac"，第一次匹配：
第二次匹配：
第三次匹配：
C代碼實(shí)現(xiàn)：
int brute_force_match(char *t, char *p) { int i, j, tem; int tlen = strlen(t), plen = strlen(p); for(i = 0, j = 0; i <= tlen - plen; i++, j = 0) { tem = i; while(t[tem] == p[j] & j < plen) { tem++; j++; } // matched if(j == plen) { return i; } } // [p] is not a substring of [t] return -1; }時(shí)間復(fù)雜度：i在主串移動(dòng)次數(shù)（外層的for循環(huán)）有n?pn?p次，在失配時(shí)j移動(dòng)次數(shù)最多有p?1p?1次（最壞情況下）；因此，復(fù)雜度為O(n?p)O(n?p)。
我們仔細(xì)觀察暴力匹配方法，發(fā)現(xiàn)：失配后下一次匹配，
- 主串的起始位置 = 上一輪匹配的起始位置 + 1；
- 模式串的起始位置 = 首字符P[0]。
如此未能利用已經(jīng)匹配上的字符的信息，造成了重復(fù)匹配。舉個(gè)例子，比如：第一次匹配失敗時(shí)，主串、模式串失配位置的字符分別為?a?與?c，下一次匹配時(shí)主串、模式串的起始位置分別為T[1]與P[0]；而在模式串中c之前是ab，未有重復(fù)字符結(jié)構(gòu)，因此T[1]與P[0]肯定不能匹配上，這樣造成了重復(fù)匹配。直觀上，下一次的匹配應(yīng)從T[2]與P[0]開始。
2. KMP算法
KMP思想
根據(jù)暴力方法的缺點(diǎn)，而引出KMP算法的思想。首先，一般化匹配失敗，如下圖所示：
在暴力匹配方法中，下一次匹配開始時(shí)，主串指針會(huì)回溯到i+1，模式串指針會(huì)回退到0。那么，如果不讓主串指針發(fā)生回溯，模式串的指針應(yīng)回退到哪個(gè)位置才能保證正確匹配呢？首先，我們從上圖中可以得到已匹配上的字符：
?
T[i…i+j?1]=P[0…j?1]T[i…i+j?1]=P[0…j?1]?
KMP算法思想便是利用已經(jīng)匹配上的字符信息，使得模式串的指針回退的字符位置能將主串與模式串已經(jīng)匹配上的字符結(jié)構(gòu)重新對(duì)齊。當(dāng)有重復(fù)字符結(jié)構(gòu)時(shí)，下一次匹配如下圖所示：
從圖中可以看出，下一次匹配開始時(shí)，主串指針在失配位置i+j，模式串指針回退到m+1；模式串的重復(fù)字符結(jié)構(gòu)：
?
T[i+j?m?1…i+j?1]=P[j?m?1…j?1]=P[0…m](1)(1)T[i+j?m?1…i+j?1]=P[j?m?1…j?1]=P[0…m]?
且有
?
T[i+j]≠P[j]≠P[m+1]T[i+j]≠P[j]≠P[m+1]?
那么應(yīng)如何選取mm值呢？假定有滿足式子(1)(1)的兩個(gè)值m1>m2m1>m2，如下圖所示：
如果選取m=m2m=m2，則會(huì)丟失m=m1m=m1的這一種字符匹配情況。由數(shù)學(xué)歸納法容易知道，應(yīng)取所有滿足式子(1)(1)中最大的mm值。
KMP算法中每一次的匹配，
- 主串的起始位置 = 上一輪匹配的失配位置；
- 模式串的起始位置 = 重復(fù)字符結(jié)構(gòu)的下一位字符（無重復(fù)字符結(jié)構(gòu)，則模式串的首字符）
模式串P="abcac"匹配主串T="ababcabcacbab"的KMP過程如下圖：
部分匹配函數(shù)
根據(jù)上面的討論，我們定義部分匹配函數(shù)（Partial Match，在數(shù)據(jù)結(jié)構(gòu)書[2]稱之為失配函數(shù)）：
?
f(j)={max{m}?1P[0…m]=P[j?m…j],0≤m<jelsef(j)={max{m}P[0…m]=P[j?m…j],0≤m<j?1else?
其表示字符串P[0…j]P[0…j]的前綴與后綴完全匹配的最大長(zhǎng)度，也表示了模式串中重復(fù)字符結(jié)構(gòu)信息。KMP中大名鼎鼎的next[j]函數(shù)表示對(duì)于模式串失配位置j+1，下一輪匹配時(shí)模式串的起始位置（即對(duì)齊于主串的失配位置）；則
?
next[j]=f(j)+1next[j]=f(j)+1?
如何計(jì)算部分匹配函數(shù)呢？首先來看一個(gè)例子，模式串P="ababababca"的部分匹配函數(shù)與next函數(shù)如下：
| P[j] | a | b | a | b | a | b | a | b | c | a | ? |
| f(j) | -1 | -1 | 0 | 1 | 2 | 3 | 4 | 5 | -1 | 0 | ? |
| next[j] | 0 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 0 | 1 | ? |
模式串的f(j)滿足P[0…f(j)]=P[j?f(j)…j]P[0…f(j)]=P[j?f(j)…j]，在計(jì)算f(j+1)分為兩類情況：
- 若P[j+1]=P[f(j)+1]P[j+1]=P[f(j)+1]，則有P[0…f(j)+1]=P[j?f(j)…j+1]P[0…f(j)+1]=P[j?f(j)…j+1]，因此f(j+1)=f(j)+1。
- 若P[j+1]≠P[f(j)+1]P[j+1]≠P[f(j)+1]，則要從P[0…f(j)]P[0…f(j)]中找出滿足P[f(j+1)]=P[j+1]的f(j+1)，從而得到P[0…f(j+1)]=P[j+1?f(j+1)…j+1]P[0…f(j+1)]=P[j+1?f(j+1)…j+1]
其中，根據(jù)f(j)的定義有：
?
P[j]=P[f(j)]=P[f(f(j))]=?=P[fk(j)]P[j]=P[f(j)]=P[f(f(j))]=?=P[fk(j)]?
其中，fk(j)=f(fk?1(j))fk(j)=f(fk?1(j))。通過上面的例子可知，函數(shù)fk(j)fk(j)是隨著kk遞減的，并最后收斂于-1。此外，P[j]與p[j+1]相鄰；因此若存在P[f(j+1)]=P[j+1]，則必有
?
f(j+1)=fk(j)+1f(j+1)=fk(j)+1?
為了求滿足條件的最大的f(j+1)，因fk(j)fk(j)是隨著kk遞減的，故應(yīng)為滿足上式的最小kk值。
綜上，部分匹配函數(shù)的計(jì)算公式如下：
?
f(j)={fk(j?1)+1?1minkP[fk(j?1)+1]=P[j]elsef(j)={fk(j?1)+1minkP[fk(j?1)+1]=P[j]?1else?
代碼實(shí)現(xiàn)
部分匹配函數(shù)（失配函數(shù)）的C實(shí)現(xiàn)代碼：
int *fail(char *p) { int len = strlen(p); int *f = (int *) malloc(len * sizeof(int)); f[0] = -1; int i, j; for(j = 1; j < len; j++) { for(i = f[j-1]; ; i = f[i]) { if(p[j] == p[i+1]) { f[j] = i + 1; break; } else if(i == -1) { f[j] = -1; break; } } } return f; }KMP的C實(shí)現(xiàn)代碼：
int kmp(char *t, char *p) { int *f = fail(p); int i, j; for(i = 0, j = 0; i < strlen(t) && j < strlen(p); ) { if(t[i] == p[j]) { i++; j++; } else if(j == 0) i++; else j = f[j-1] + 1; } return j == strlen(p) ? i - strlen(p) : -1; }時(shí)間復(fù)雜度：fail函數(shù)的復(fù)雜度為O(p)O(p)，kmp函數(shù)的復(fù)雜度為O(n)O(n)，所以整個(gè)KMP算法的復(fù)雜度為O(n+p)O(n+p)。
轉(zhuǎn)載于:https://www.cnblogs.com/yulei126/p/6756233.html
總結(jié)
以上是生活随笔為你收集整理的KMP算法的来龙去脉的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： poj2019（二维RMQ）
- 下一篇： 解析html文档的java库及范例