看數(shù)據(jù)結(jié)構(gòu)的書，字符串章節(jié)提到這個(gè)字符串匹配的算法。結(jié)果一看，真是比較難理解，不愧是三個(gè)人想出來的算法，以三個(gè)人的名字命名這個(gè)算法KMP。書上講的也是看不明白，只能上網(wǎng)搜搜比較通俗易懂的回答 。結(jié)果大部分都是復(fù)制粘貼，提到遞歸什么的，越看越糊涂，估計(jì)作者自己都不明白。后來還是在知乎上看到一個(gè)點(diǎn)贊數(shù)比較多的，結(jié)果一看，講的不錯(cuò)。知乎不愧是程序員用戶比較多的平臺(tái)，大神就是吊。
自己看了看，想了想，動(dòng)手抄一遍，運(yùn)行一下，加深記憶理解。
原文地址： 鏈接
直接開始廢話，也都是抄這位作者的，只是為了自己寫一遍
一、問題：定位出一個(gè)字符串在另一個(gè)字符串中完全匹配的位置。
比如目標(biāo)字符串：abcabcdee 主字符串：xyzabcabcdeezzz
明顯一看，結(jié)果就是3。在第3位置的a開始匹配到最后。
如果用樸素方法，直接遍歷，兩個(gè)字符串挨個(gè)對(duì)比，如果不匹配，目標(biāo)字符串從頭開開始，主字符串回到上次匹配位置的下一個(gè)位置。每次不匹配的時(shí)候，都需要從頭開始。最差情況下，主字符串從頭到最后，目標(biāo)字符串每次都是到最后一個(gè)字符不匹配，所以時(shí)間復(fù)雜度就是O（m*n）。
二、樸素方法的弊端
樸素方法每次匹配失敗的時(shí)候都要從頭開始，比如匹配到第6個(gè)字符失敗了，如果知道了失敗了的位置之前到字符串，也就是前5個(gè)字符的前綴和后綴的交集，就可以從這個(gè)交集長度的位置開始下次匹配了，這樣，目標(biāo)字符串不用從0開始，主字符串也不用回溯到上一次開始的地方了。就節(jié)省了很多步。
三、字符串前綴和后綴的交集
前綴：一個(gè)字符串的子字符串，確保包含第一個(gè)字符，但不包含自身。
后綴：一個(gè)字符串的子字符串，確保包含最后一個(gè)字符，但不包含自身。
比如：abab
前綴集合：a、ab、aba。后綴集合：b、ab、bab。
所以集合的交集是ab。交集可能不止一個(gè)。需要的是最大長度。
有了前后綴交集的長度，說明可以重疊著么長，既然都重疊了，說明前面重疊部分不需要對(duì)比了，直接從重疊的下一個(gè)位置開始就行了。
KMP的關(guān)鍵就是求目標(biāo)字符串每個(gè)位置的前后綴交集里最大長度。
四、部分匹配表
比如：字符串“abababca”
首先，對(duì)于這個(gè)數(shù)組，最后一個(gè)位置的值是用不上的。因?yàn)檫@個(gè)表的用處是在匹配失敗的時(shí)候需要回溯，回溯位置是前面子字符串的表值+1。
比如目標(biāo)這個(gè)字符串長度是8，匹配到位置6失敗了，這時(shí)候需要回溯到前5個(gè)子字符串，第5位置的值是2，這時(shí)候需要回溯到3。從3位置的字符開始接著匹配。
媽的，亂七八糟，說不清。
所以真正用到的值是當(dāng)前位置前一個(gè)位置的表值，最有一個(gè)位置的值只能在全部匹配完的時(shí)候才用到，但是全部匹配完意味著匹配成功，找到結(jié)果了，更用不上它了。所以最后一個(gè)值沒什么卵用。
而且為了編程方便，就把每個(gè)位置對(duì)應(yīng)的值往后推了一格，把最后一個(gè)扔了，反正也用不上，第一個(gè)空了出來，用-1代替。所以一般叫next數(shù)組。匹配失敗的時(shí)候，回溯位置也不用上一個(gè)位置的值+1了，直接就是自己位置對(duì)應(yīng)的值了。
void getNext(char *p, int *arr) {
int i = 0;
int j = -1;
arr[0] = -1;
while (i < strlen(p)-1) {
if (j == -1 || p[i] == p[j]) {
I++;
j++;
arr[i] = j;
}else{
j = arr[j];
}
}
}
跟著流程走一下，可以發(fā)現(xiàn)，這個(gè)匹配表的前兩位固定是-1、0
i的位置表示自己的后綴字符串，j表示前綴字符串。
這里比較繞，說不清，真雞兒難。該睡覺了。
KMP
int kmpMethod(char *str, char *target, int *next) {
int i = 0;
int j = 0;
while (i < strlen(str) && j < (int)strlen(target)) {
if (j == -1 || str[i] == target[j]) {
I++;
j++;
}else{
j = next[j];
}
}
if (j == strlen(target)) {
return i - j;
}
return -1;
}
匹配成功，各自往后走，各個(gè)位置+1。
如果匹配失敗，就找當(dāng)前位置的前面子字符串的匹配表的值，意味找最大重合部分，如果有重合部分，就不用比較前面的了，直接從重合部分開始比較后面的。如果當(dāng)前位置前面子字符串值是0，意味著沒有重合部分，就縮小范圍，尋找上一個(gè)子字符串的前后綴重合部分，有的話就開始匹配，沒有的話，就接著尋找上上一個(gè)，直到值是-1，意味著當(dāng)前位置前面的子字符串沒有一個(gè)完全沒有重疊的部分，就只能從頭開始，就各自+1，目標(biāo)字符串從頭開始了，回溯到0，主字符串是一直往后走的，不回溯。
注：strlen得到無符號(hào)整型，j的值是-1的時(shí)候，會(huì)出現(xiàn)-1>無符號(hào)數(shù)值的問題，所以需要用int強(qiáng)轉(zhuǎn)一下。
說不明白，哈哈?？偟膩碚fKMP算法過程容易理解，求部分匹配表那個(gè)算法比較難理解。反正這陣子睡眠不好，剛好記錄一下。想看的時(shí)候直接來簡書看，方便。
