先注明抒寂，本文章轉(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è)往往都會(huì)比模式串更長的那個(gè))
2.模式串：就是那個(gè)檢查在目標(biāo)串中是否匹配的那個(gè)串
在KMP算法中睡蟋，模式給我們提供了一個(gè)工具踏幻，通過這個(gè)工具，使得我們減少了時(shí)間戳杀，這個(gè)工具就是next函數(shù)（這個(gè)就是KMP算法中最難理解的一部分）该面。
一般來說夭苗，我們在比較兩個(gè)串的時(shí)候，都是采用先比較各個(gè)位置隔缀，要是不對题造，就將指向模式串的指針復(fù)原，即下一次檢查就從模式串的開頭來看猾瘸。 然后指向目標(biāo)串的指針向后移動(dòng)一個(gè)位置晌梨。
但是KMP算法告訴我們，其實(shí)在移動(dòng)時(shí)候须妻，我們不必要傻傻地移動(dòng)一位，而移動(dòng)的位數(shù)泛领，我們可以通過我們要比對的對象知道荒吏。 而把這個(gè)移動(dòng)的位數(shù)，或者說是下一個(gè)要比對的對象下標(biāo)記下來渊鞋，那么之后遇到在這個(gè)點(diǎn)不匹配的時(shí)候绰更，我就直接移動(dòng)到對應(yīng)的位置，而不需要只移動(dò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)榱就琻ext函數(shù)的生成就是按照KMP算法本身來產(chǎn)生的宜咒。 試想一下，next函數(shù)不正是在同一個(gè)串內(nèi)的字符串的比較么把鉴？ 為了理解這個(gè)故黑，我廢了很大功夫
我做了這樣的一個(gè)假設(shè)： 兩個(gè)空字符一定相等。這一點(diǎn)非常重要

那么用遞推公式給出next 如果前面的已經(jīng)匹配好了庭砍。（先不管匹配了有多長场晶，是從哪開始了） 但是我們保證了前面的那個(gè)一定是匹配好的。
我們可以做上面的假設(shè)的原因就是我們之前講到的那個(gè)空字符一定是相等的怠缸，那么我就可以說這對空字符是匹配好的
因?yàn)樽钚∈幔覀兌伎梢哉f有一對空字符相等，所以揭北，就可以做上面的假設(shè)扳炬。
那么就開始匹配了。我們在這里恰好使用以模式串開頭部分作為了我們所說的模式串搔体。(這就是前綴)
將next[0]設(shè)置為-1恨樟。 意思是，如果這個(gè)不匹配疚俱，就用next[-1]來和這個(gè)開頭的不匹配的字符來進(jìn)行匹配劝术。 但是next[-1]是不存在是，在我的這里计螺，就假設(shè)為了那個(gè)空字符串夯尽。
所以，就是將這個(gè)最開頭那個(gè)空的(不存在的)那個(gè)字符登馒，匹配當(dāng)前的串匙握，不就是將整個(gè)串向后移動(dòng)一位(至少對于第一個(gè)串中不匹配的對象是這樣的)。
到這里陈轿，關(guān)于為什么next[0]要取-1要清楚了
之后呢圈纺，往下走。如果這個(gè)位置都匹配的麦射，那么下面向下移動(dòng)的之后的那個(gè)位置(假設(shè)匹配不對的位置)蛾娶，每一個(gè)串是前面那個(gè)字符的匹配情況加一。本質(zhì)上是雙方本來就往后移動(dòng)了潜秋，那么就直接賦值就好了蛔琅。
如果不匹配，那么由于我們采用的是前面是模式串峻呛，后面是目標(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來匹配色徘，也就是后移動(dòng)一位 
    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來匹配蝌借，也就是后移動(dòng)一位 
    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原文鏈接
有彩色字缀磕，可能會(huì)更好看一點(diǎn)缘圈。

歡迎關(guān)注我的公眾號：肥宅Sean筆記

肥宅Sean筆記