先注明，本文章轉(zhuǎn)載于自己的CSDN博客
KMP算法用于字符匹配工作
樸素匹配方法的復(fù)雜度是O(N*M)
KMP算法復(fù)雜度達(dá)到了O(N+M)
從這表達(dá)式來說，復(fù)雜度明顯地降低了
但這個(gè)算法最大的問題，就是很難理解。 在網(wǎng)上看了很多人，包括有個(gè)哥大家都說他講得已經(jīng)是最好的那個(gè)了，但是我還是沒有看明白他在說什么，只是大概了解了他的思路。
回去之后，翻了下數(shù)據(jù)結(jié)構(gòu)和算法的書，認(rèn)認(rèn)真真地看了遍，收獲很大。 特在這做一下筆記，方便大家一起學(xué)習(xí)。
KMP算法的意思就是(這里采用我在很多書上看到的理解之后的一個(gè)匯總版) 在那之前，我們要明白兩個(gè)東西
1.目標(biāo)串：就是我們要比對的串(就是那個(gè)往往都會比模式串更長的那個(gè))
2.模式串：就是那個(gè)檢查在目標(biāo)串中是否匹配的那個(gè)串
在KMP算法中，模式給我們提供了一個(gè)工具，通過這個(gè)工具，使得我們減少了時(shí)間，這個(gè)工具就是next函數(shù)（這個(gè)就是KMP算法中最難理解的一部分）。
一般來說，我們在比較兩個(gè)串的時(shí)候，都是采用先比較各個(gè)位置，要是不對，就將指向模式串的指針復(fù)原，即下一次檢查就從模式串的開頭來看。 然后指向目標(biāo)串的指針向后移動一個(gè)位置。
但是KMP算法告訴我們，其實(shí)在移動時(shí)候，我們不必要傻傻地移動一位，而移動的位數(shù)，我們可以通過我們要比對的對象知道。 而把這個(gè)移動的位數(shù)，或者說是下一個(gè)要比對的對象下標(biāo)記下來，那么之后遇到在這個(gè)點(diǎn)不匹配的時(shí)候，我就直接移動到對應(yīng)的位置，而不需要只移動一位，這樣就節(jié)省了時(shí)間。
而這個(gè)儲存，我們就是采用next實(shí)現(xiàn)的，不管你之前是看了多少其他的說法，請把之前對于next函數(shù)的看法放到一邊，再認(rèn)真看我下面的文字
這里采用的是，next[j] = k 表示，第j個(gè)位置的模式串和對應(yīng)的目標(biāo)串中的字符不匹配的時(shí)候，就用第k位的，模式串中字符和目標(biāo)串的失配的位置進(jìn)行比較
next函數(shù)不僅僅表示了位置，同時(shí)也描述了長度，這點(diǎn)在后面的文字中慢慢理解，這里先講述出來
看到這里，你可以理解了KMP算法的大致操作了。如果沒有，請?jiān)倏匆槐樯厦娴奈淖?，一個(gè)被稱之為難的算法，只看一遍就能懂，那真是很高的傳授技術(shù)加上雙方的好運(yùn)了。
next函數(shù)的生成，可以說是最難理解的一部分，但是，我相信，這也只是臨門一腳的問題。 因?yàn)?，next函數(shù)的生成就是按照KMP算法本身來產(chǎn)生的。 試想一下，next函數(shù)不正是在同一個(gè)串內(nèi)的字符串的比較么？ 為了理解這個(gè)，我廢了很大功夫
我做了這樣的一個(gè)假設(shè)： 兩個(gè)空字符一定相等。這一點(diǎn)非常重要
那么用遞推公式給出next 如果前面的已經(jīng)匹配好了。（先不管匹配了有多長，是從哪開始了） 但是我們保證了前面的那個(gè)一定是匹配好的。
我們可以做上面的假設(shè)的原因就是我們之前講到的那個(gè)空字符一定是相等的，那么我就可以說這對空字符是匹配好的
因?yàn)樽钚?，我們都可以說有一對空字符相等，所以，就可以做上面的假設(shè)。
那么就開始匹配了。我們在這里恰好使用以模式串開頭部分作為了我們所說的模式串。(這就是前綴)
將next[0]設(shè)置為-1。 意思是，如果這個(gè)不匹配，就用next[-1]來和這個(gè)開頭的不匹配的字符來進(jìn)行匹配。 但是next[-1]是不存在是，在我的這里，就假設(shè)為了那個(gè)空字符串。
所以，就是將這個(gè)最開頭那個(gè)空的(不存在的)那個(gè)字符，匹配當(dāng)前的串，不就是將整個(gè)串向后移動一位(至少對于第一個(gè)串中不匹配的對象是這樣的)。
到這里，關(guān)于為什么next[0]要取-1要清楚了
之后呢，往下走。如果這個(gè)位置都匹配的，那么下面向下移動的之后的那個(gè)位置(假設(shè)匹配不對的位置)，每一個(gè)串是前面那個(gè)字符的匹配情況加一。本質(zhì)上是雙方本來就往后移動了，那么就直接賦值就好了。
如果不匹配，那么由于我們采用的是前面是模式串，后面是目標(biāo)串的抽象定義。就是說，前面那些字符的next值已經(jīng)算好了的，那么就直接用前面算好的next值進(jìn)行回溯。 用之前KMP的算法的思路，就實(shí)現(xiàn)了所有模式串的next值。 next值生成代碼如下：
void getNext(int next[]) {
int j = 0, k = -1, length = str.size();
// 其中k表示的是前面的那個(gè)串，而j表示的是后面那個(gè)串，用同一個(gè)串的不同起始點(diǎn)的串進(jìn)行比較
// 前面的那個(gè)串去匹配后面的那個(gè)串，通過這個(gè)方式來進(jìn)行匹配(也是一個(gè)KMP)
next[0] = -1; // 表示如果開頭不能匹配，就用這個(gè)前面那個(gè)-1來匹配，也就是后移動一位
while(j < length) {
if (k == -1 || str[j] == str[k]){
j ++; k ++;
next[j] = k;
} else {
k = next[k];
}
}
}
看完上面的文字，就要把KMP算法看懂了，之后再看hiho1015
和一般的KMP不同，這一題，要求對于匹配出來的串進(jìn)行計(jì)數(shù)。
就是看究竟匹配了幾次？
對于原來的KMP的改的地方就是
if (k == str.size()) {
ans += 1;
k = next[k];
}
加了上這個(gè)函數(shù)地方。
這里的意思是，如果匹配完成了，就將計(jì)數(shù)數(shù)字加一，并且，將原來的進(jìn)行回溯，如果這個(gè)回溯理解不了，那么是因?yàn)榍懊娴腒MP還沒有看懂，要再看一次，就可以明白，這里保證不管對不對，在這個(gè)串的位置，一定是不匹配的（你的長度都超過了還能對？？？），那就一定要回溯。
文末有原題鏈接
代碼如下：
#include <iostream>
using namespace std;
string str, ptr;
void getNext(int next[]) {
int j = 0, k = -1, length = str.size();
// 其中k表示的是前面的那個(gè)串，而j表示的是后面那個(gè)串，用同一個(gè)串的不同起始點(diǎn)的串進(jìn)行比較
// 前面的那個(gè)串去匹配后面的那個(gè)串，通過這個(gè)方式來進(jìn)行匹配(也是一個(gè)KMP)
next[0] = -1; // 表示如果開頭不能匹配，就用這個(gè)前面那個(gè)-1來匹配，也就是后移動一位
while(j < length) {
if (k == -1 || str[j] == str[k]){
j ++; k ++;
next[j] = k;
} else {
k = next[k];
}
}
}
int KMP_Ans(int next[]) {
int j = 0, k = 0, length = ptr.size(), ans = 0;
while (j < length) {
if (k == -1 || str[k] == ptr[j]) {
j ++; k ++;
if (k == str.size()) {
ans += 1;
k = next[k];
}
} else {
k = next[k];
}
}
return ans;
}
int main(){
int time;
cin >> time;
while (time--){
cin >> str>> ptr;
int *a = new int [str.size() + 1];// 將數(shù)組開稍微大點(diǎn)
getNext(a);
cout << KMP_Ans(a)<< endl;
delete[] a;
}
}
hihocoder原題鏈接
但要登錄好了之后，才能直接跳轉(zhuǎn)到題目，否則就是只有登錄鏈接，不過可以登錄完了之后，再來點(diǎn)擊這個(gè)，也就可以直接訪問了。
CSDN原文鏈接
有彩色字，可能會更好看一點(diǎn)。
歡迎關(guān)注我的公眾號：肥宅Sean筆記
