問題描述
KMP算法是用與字符串匹配的算法幢泼，給定文本串，在文本串中尋找模式串征唬，如果找到匹配的模式串便返回文本串首次出現(xiàn)模式串的首字符的地址
算法分析
1th
最簡單最暴力的算法便是逐一匹配全部字串格嘁，該算法的時(shí)間復(fù)雜度為O(m*n)，其中m為文本字符數(shù)奏窑，n為字串?dāng)?shù)
思路如圖示：
遇到匹配失敗后
逐一遍歷文本串，來匹配模式串屈扎，直至匹配成功埃唯，或者匹配到最后無可匹配
Code
char text[m];
char pattern[n];
for ( i = 0; i < m; i++) {
for ( j = 0; j < n && (i + j) < m; j++) {
if (pattern[j] != test[j + n]) {
break;
}
}
if (j == n) {
return true;
}
}
return false;
2th
為什么1th版本會(huì)很慢？是因?yàn)樽隽撕芏嗟臒o效匹配鹰晨，以上面的例子為例墨叛，當(dāng)遍歷到text[3]時(shí)匹配失敗止毕，指針退回了text[1]。每一次失敗的匹配只會(huì)重新在下一位繼續(xù)匹配漠趁。從上述例子可以看出從text[1]繼續(xù)下去匹配只會(huì)還是失敗扁凛。這便是為什么慢的原因
這里事先說明，這里所說的指針不是C語言中的指針闯传，是更范的概念谨朝，表示所指元素的地址（不一定是計(jì)算機(jī)內(nèi)部的地址，可以是數(shù)組下標(biāo)
i為模式串的指針
j為文本串的指針
KMP的算法便做了一個(gè)優(yōu)化甥绿，i不會(huì)回退字币，每一次遍歷只會(huì)向前，不會(huì)像前面那樣妹窖，從text[3]的匹配失敗回退到text[1]。
如圖所示：
匹配失敗
回退之后收叶，匹配成功：
再次失斀竞簟：
回退之后，再次失敗判没，但是無法回退了：
直到最后匹配成功或者失敗
總結(jié)一下圖中所示：遍歷文本串的指針是不會(huì)后退的蜓萄，只會(huì)一直向前。會(huì)后退的是模式串的指針
每次pattern[i]匹配失敗澄峰，對(duì)應(yīng)的文本串的 j 指針便會(huì)回退到一個(gè)合適的位置（什么是合適的位置嫉沽？后面將會(huì)詳細(xì)的講解）然后從這個(gè)位置再繼續(xù)匹配，如果仍舊匹配失敗俏竞，繼續(xù)回退绸硕，直到匹配成功或者不能再回退為止。
無論最后合適的位置是否匹配魂毁，i 都會(huì)向前
Code
bool KMP(char text[], char pattern[]) {
int n = strlen(text);
int m = strlen(pattern);
getNext(pattern, m);
int j = -1;
for (int i = 0; i < n; i++) {
while (j != -1 && text[i] != pattern[j + 1]){//尋找合適位置玻佩，直到匹配成功或者無可回退
j = next[j];
}
if (text[i] == pattern[j + 1]) {//在pattern[i]匹配成功，移動(dòng) j
j++;
}
if (j == m - 1) {//表示匹配成功
return true;
}
}
return false;
}
注意上面text[j + 1]才是和pattern[i]相匹配的, j 是相匹配下標(biāo)的前一位
j = next[j];便代表 j 的回退席楚，而next數(shù)組正是管理著文本串每個(gè)字符的回退下標(biāo)咬崔，也就是所謂的合適位置
下面開始講解Next數(shù)組
Next數(shù)組
假設(shè)一個(gè)字符串s和一個(gè)next數(shù)組（長度相等且為l）
next[k]（k <= l )里的值等于s的子串n[0....k]的最長相等前后綴的前綴最后一個(gè)元素的下標(biāo)，如果找不到相等的前后綴烦秩，便取-1垮斯；
如圖所示：
字符字串n = abcab的最長前后綴為ab，所以next[4] = 1
而整個(gè)next數(shù)組里存放的值便是字符串s(長度為n）的字符字串[0....k](k <= n)的最長相等前后綴的前綴最后一個(gè)元素的下標(biāo)只祠，如果沒有相等的前后綴兜蠕，便設(shè)為-1
也許有人還不明白這最長前后綴的作用，那么便解釋一下：
當(dāng)pattern[i] != text[j+1]時(shí)抛寝，我們便找到字符串k[0...j]的最長前綴的下標(biāo)牺氨，從該最長前綴繼續(xù)往下匹配(通過更新j來繼續(xù)匹配 j = next[j])*狡耻，如果還不匹配再找該前綴的最長前綴的下標(biāo)，直到找到可以匹配或者j = -1
那么如何求出next數(shù)組的值呢猴凹？
假設(shè)我們有一個(gè)字符串s[0...k]夷狰，并且已知next[0....k-1]的值，現(xiàn)在我們要求next[k]
那么我們?cè)趺辞竽亟荐恳驗(yàn)槲覀冇辛俗址畁[0....k-1]相對(duì)應(yīng)的next[]值沼头，所以我們就可以通過比較s[k]是否等于n[0...k-1]的最長子綴的后一位字符來確定next[k]!，如果相同意味著next[k] = next[k - 1] + 1书劝，如果不相同进倍，便找m[0...next[k - 1]]的后一位元素相比較，因?yàn)閱栴}條件中next[0...k-1]我們都是知道的购对！猾昆，一直往下遞歸，直到找到有個(gè)前綴的后一個(gè)元素與之相同（這個(gè)就是s[0...k]的最大前綴骡苞，仔細(xì)想想）或者沒有前綴與之相等（設(shè)為-1）
Notice垂蜗！next[n]里的的值代表字符串m[0...n]的最長前綴的最后一位元素的下標(biāo)，不要弄暈了
好了解幽，求法我們已經(jīng)完成了一大半贴见。如果我們有字符串s[0...k+1], 并且已知next[0...k]的值，然后求next[k+1]躲株，這個(gè)過程是否似曾相識(shí)呢片部？
我們只需設(shè)定next[0] = -1；便可以一直往下推出剩下的next值（假定只有一個(gè)字符的串沒有相等的前后綴）
Code
void getNext(char s[], int length) {
int j = -1;
next[0] = j;
for (int i = 1; i < length; i++) {
while (j != -1 && s[i] != s[j + 1]) {//不退ǎ回退档悠，直到找到或者等于j = -1
j = next[j];
}
if (s[i] == s[j + 1])//找到
j++;
next[i] = j;
}
}
next數(shù)組和kmp結(jié)合起來一看，便是當(dāng)k+1匹配失敗之后望浩，k便回退到next[k]繼續(xù)匹配站粟，直到可以匹配或者k = -1重新匹配
next找到最大前綴，kmp使用最大前綴來實(shí)現(xiàn) i 一直向前遍歷
nextval數(shù)組
nextval是next的高配版曾雕，next數(shù)組存在多次更新情況奴烙，也就是可能回退多次才能找到最終合適的位置，而nextval一步到位直接找到最合適的位置
s[0...4] = ababa 最大前綴為aba aba的最大前綴為a
如果s的[5] = b,如果匹配失敗剖张，便會(huì)繼續(xù)匹配s[3], s[1]而它們也正好都是b切诀，因此多了幾次無謂的比較
所以一旦s[5]比較失敗，便直接回退到-1搔弄，也就是其該字串的前綴之后的第一個(gè)元素不等于該字串的之后的第一個(gè)元素的最大前綴
只需添加s[j + 1] == s[i +1]這一判斷條件
如果成立幅虑，nextval[j] = nextval[i];
否則，nextval[j] = i;
Summary
總的來說顾犹，KMP是利用了最大前綴來節(jié)省了時(shí)間倒庵，保證pattern一直向前遍歷褒墨，而且text串也最大程度地節(jié)省了匹配位數(shù)
KMP算法是AC自動(dòng)機(jī)的特殊情況，有興趣可以閱讀之后AC自動(dòng)機(jī)講解
