串匹配算法也稱作模式匹配算法，就是在目標(biāo)字符串中查找子字符串讹堤，常用于文本搜索吆鹤、入侵檢測(cè)等領(lǐng)域，將目標(biāo)字符串定義為T(t0,t1,... tn-1)洲守，將模式字符串定義為P(p0,p1...pm-1)疑务。下面將來逐步講解算法之美中的KMP算法。
1.BF算法
最簡(jiǎn)單的做法就是遍歷目標(biāo)字符串中的每一個(gè)字符與模式字符串中的字符進(jìn)行逐一比較梗醇，不相同的時(shí)候保持目標(biāo)字符串的索引不變模式字符串的索引加1知允，在進(jìn)行逐個(gè)字符的比較，這種方式也稱作BF（Brute Force）算法叙谨，如下圖所示：
由此可見温鸽，BF算法的時(shí)間復(fù)雜度為O((n-m)*m)，該方法簡(jiǎn)單手负、直觀，但是由于每遇到一次失配都要將目標(biāo)字符串的索引回溯，顯然效率很低。
2.MP算法
MP算法是由詹姆斯·莫里斯和沃恩·普萊特在1970年提出的一種快速匹配算法。該算法的主要特點(diǎn)是當(dāng)失配情況發(fā)生時(shí)撵渡，目標(biāo)字符串的索引不需要回溯，利用模式字符串的內(nèi)部特征可以完全避免目標(biāo)字符串的回溯充岛，這樣可以極大的提高檢索效率盹憎。先舉一個(gè)簡(jiǎn)單的例子對(duì)于目標(biāo)字符串a(chǎn)babcababd與模式字符串a(chǎn)babd來說：
第一次失配發(fā)生在
t[i = 4] = c 和 p[j = 4] = d 處如果按照BF檢索的話，下一次比較時(shí)字符串T和字符串P的起始位置分別為1和0瘾境，但是這樣做完全沒有必要歧杏，通過觀察模式字符串可以發(fā)現(xiàn)，ababd中前四個(gè)字符具有相同的特征就是a[0]a[1] = a[2]a[3]迷守，那么下次匹配時(shí)犬绒，就不需要將目標(biāo)字符串的索引回溯，我們只需要將模式字符串的索引位置變?yōu)閖 = 2就可以進(jìn)行下輪的比較：
此時(shí)發(fā)現(xiàn)t[4] != p[2]兑凿，需要比較t[4]與p[0]得到如下圖：
發(fā)現(xiàn)t[4] != p[0]凯力，然后將i加1，再與p進(jìn)行比較：
逐個(gè)比較之后發(fā)現(xiàn)完全相等礼华。
MP算法就是在對(duì)字符串進(jìn)行匹配之前咐鹤，先求出模式字符串中各個(gè)字符間的關(guān)系（由于模式字符串在進(jìn)行匹配之前就可以確定），然后依據(jù)此關(guān)系與目標(biāo)字符串進(jìn)行匹配圣絮。記錄模式字符串P中各個(gè)字符之間的關(guān)系的函數(shù)也叫作字符串的失效函數(shù)祈惶。讓我們先來看看這個(gè)失效函數(shù)，先舉一個(gè)簡(jiǎn)單的例子：目標(biāo)字符串為aaaaab與模式字符串aaab的比較扮匠，當(dāng)?shù)谝惠啽容^到i=3時(shí)捧请，失配發(fā)生了，此時(shí)t[i] = a 與 p[i] = b不相等棒搜，由于模式字符串在i=3之前的字符都與目標(biāo)字符串的字符相同即：t[0]t[1]t[2] = p[0]p[1]p[2]疹蛉，而且模式字符串中的前三個(gè)字符也完全相同即：p[0]=p[1]=p[2]那么下次比較的位置我們能準(zhǔn)確的定位：目標(biāo)字符串t[3]與模式字符串p[2]進(jìn)行比較，因?yàn)?code>t[1] = p[0] ;t[2] = p[1]力麸，所以如果從t[1]開始逐個(gè)與模式字符串中的字符比較就會(huì)造成浪費(fèi)可款。失效函數(shù)是記錄當(dāng)失配發(fā)生時(shí)，模式字符串索引應(yīng)該跳轉(zhuǎn)的位置末盔。
<b>我們用f(i)記錄當(dāng)失配發(fā)生時(shí)筑舅，模式字符串應(yīng)該回退的索引位置，則定義如下：對(duì)于長(zhǎng)度為n的字符串陨舱，位于第m位的字符如果存在如下關(guān)系：p[0]...p[k] = p[m-k]...p[m]翠拣，且滿足該條件的k最大，那么f[m]=k游盲，若不存在f(i) = 1误墓，其中n > m , m > k蛮粮。</b>，當(dāng)遇到失配發(fā)生時(shí)谜慌，我們只需要將模式字符串的指針移動(dòng)到f(m-1) + 1處然想，而不需要移動(dòng)目標(biāo)字符串的指針。
可以簡(jiǎn)單的論證一下當(dāng)存在匹配模式時(shí)（讀者可以自行論證當(dāng)不存在模式匹配時(shí)的情況）：對(duì)于目標(biāo)字符串T和模式字符串P（我們假設(shè)都從下標(biāo)1開始）欣范，當(dāng)T[i + 1 ... i + k - 1]的k-1個(gè)元素與P[1 ... k-1]相同变泄，但是T[i+k] 與 P[k]比較時(shí)失配，如果f(k - 1) = j ,那么根據(jù)定義P[1...j] == P[k-j... k-1]恼琼，也就是說<u>T[i+k-j...i+k-1] = P[1...j]</u>妨蛹，那么我們下次比較的就是T[i+k]與P[j+1]了，所以晴竞，當(dāng)P[k]失配時(shí)蛙卤，我們將下次比較的位置定位在P[f(k-1)+1]，我們假設(shè)next[k] = f(k-1)+1噩死，當(dāng)失配在第k個(gè)字符串發(fā)生時(shí)颤难，next[k]表示下次比較時(shí)，模式字符串的索引值已维。
下面的C代碼就是求取模式字符串的next函數(shù)如下：
void MPPattern(const char * var , int *mpArr) {
size_t length = strlen(var);
int i = 0;
int j = mpArr[0] = -1;
while (i < length) {
while (j > -1 && var[i] != var[j]) { // 4
j = mpArr[j]; // 5
}
i++; // 1
j++; // 2
mpArr[i] = j; // 3
}
}
var 即為待求解的模式字符串行嗤，將最后求得的next[]存放在mpArr中，將j衣摩、mpArr[0]賦值為-1昂验。首先看看簡(jiǎn)單的1、2艾扮、3這幾個(gè)步驟既琴，如果我們要求解的是aaaaa這樣字符全部相同的模式字符串，自然而然泡嘴，隨著字符索引的增加甫恩，next[i]根據(jù)定義也應(yīng)該是遞增+1的，這三步很好理解酌予。再來看看4磺箕、5步，如果向前遍歷的過程中x[i]!=x[j]抛虫，由于i總比j大松靡，需要將j回溯，回溯的位置就是mpArr[j]（其實(shí)就是f(k-1)+1）建椰，在進(jìn)行比較雕欺，如果j = -1(mpArr[0])時(shí)，執(zhí)行1、2屠列、3步啦逆。
對(duì)于字符串aaabc執(zhí)行的結(jié)果為
目標(biāo)字符串與模式字符串比較代碼如下：
int isTargetContain(const char* target , const char* pattern) {
size_t pLength = strlen(pattern);
int * a = calloc(pLength, sizeof(int));
MPPattern(pattern, a);
size_t tLength = strlen(target);
int i = 0 , j = 0;
while (j < tLength) {
while (i > -1 && target[j] != pattern[i]) {
i = a[i];
}
i++;
j++;
if (i >= pLength) {
int index = j - i;
i = a[i];
free(a);
return index;
}
}
free(a);
return -1;
}
其中i = a[i]依然表示的是回溯。
KMP算法
KMP算法與MP算法相似笛洛，唯一的不同點(diǎn)就是夏志，f(m)不僅要滿足p[0]...p[k-1] = p[m-k]...p[m-1]，同時(shí)要滿足條件P[k]!=P[m]苛让。KMP是在MP算法上的優(yōu)化沟蔑，在與目標(biāo)字符串比較時(shí)，T[i ... i + k - 1]的k-1個(gè)元素與P[0 ... k-1]相同狱杰，但是T[i+k] 與 P[k]比較時(shí)失配溉贿，按照MP算法的話，模式字符串應(yīng)該回溯到f(k-1)+1這個(gè)位置浦旱，如果 P[f(k-1)+1]與P[k]相同的話，再次與目標(biāo)字符串比較九杂，肯定會(huì)失敗颁湖。我們用kmpNext[]數(shù)組來記錄KMP算法下失配時(shí)模式串的偏移：
- 如果kmpNext[j] = -1 表示P[j] = P[0]，且P[j]前面k個(gè)字符與P開頭的k個(gè)字符不等例隆，或者相等但是P[j]!=P[k]
- 如果kmpNext[j] = k 表示模式字符串P中甥捺，字符P[j]前面k個(gè)字符與模式字符串開頭k個(gè)字符相同，且 P[j]!=P[k]
- 其它情況kmpNext[j] = 0
kmp計(jì)算kmpNext[]的算法實(shí)現(xiàn)如下：
void KMPPattern(const char * var , int *kmpArr) {
int i ,j;
size_t length = strlen(var);
i = 0;
j = kmpArr[0] = -1;
while (i < length) {
while (j > -1 && var[i] != var[j]) {
j = kmpArr[j];
}
i++;
j++;
if (var[i] == var[j]) { // 1
kmpArr[i] = kmpArr[j];
} else {
kmpArr[i] = j;
}
}
}
其中回溯那部分代碼與MP算法相同镀层，唯一不同的是1處的代碼镰禾，如果我們的模式字符串為aaaa，那么根據(jù)定義可知道唱逢，kmpNext[] = [-1,-1,-1,-1]吴侦，這就是var[i]==var[j]這個(gè)判斷做的事情，但是如果是字符串aaaab坞古，那么kmpNext[] = [-1,-1,-1,-1,3]备韧，最后的3就是else里做的事情，復(fù)雜的模式字符串原理大致相同痪枫，可以自行論證织堂。
kmp算法目標(biāo)字符串與模式字符串比較的代碼如下：
int KMP(const char *target , const char *pattern){
size_t targetSize = strlen(target);
size_t patternSize = strlen(pattern);
if (patternSize > targetSize) { return -1; }
int *t;
t = calloc(patternSize + 1, sizeof(int));
KMPPattern(pattern, t);
int i = 0 , j = 0;
while (j < targetSize) {
while (i > -1 && target[j] != pattern[i]) {
i = t[i];
}
i++;
j++;
if (i >= patternSize) {
free(t);
return (j - i);
}
}
free(t);
return -1;
}
結(jié)論
kmp算法由于先尋找模式字符串的內(nèi)部特征來降低與目標(biāo)字符串的匹配次數(shù)，時(shí)間復(fù)雜度為O(m + n)奶陈，在進(jìn)行匹配之前需要先將模式字符串的失效函數(shù)計(jì)算出來易阳，在進(jìn)行匹配時(shí)，如果匹配失敗吃粒，不需要將目標(biāo)字符串回溯潦俺，只需要將模式字符串的指針回溯值next[j]處從而提高效率。
