KMP算法是一種改進(jìn)的字符串匹配算法瘸彤，由D.E.Knuth壹甥，J.H.Morris和V.R.Pratt同時(shí)發(fā)現(xiàn)空幻，因此人們稱它為克努特——莫里斯——普拉特操作（簡(jiǎn)稱KMP算法）熙兔。KMP算法的關(guān)鍵是利用匹配失敗后的信息弛说，盡量減少模式串與主串的匹配次數(shù)以達(dá)到快速匹配的目的挽懦。具體實(shí)現(xiàn)就是實(shí)現(xiàn)一個(gè)next()函數(shù)，函數(shù)本身包含了模式串的局部匹配信息剃浇。時(shí)間復(fù)雜度O(m+n).
from --百度百科

---首先,我們需要更細(xì)致的了解這個(gè)算法是為了解決哪種問(wèn)題.

Q:

using namespace std;
int main(int argc, const char * argv[])
{
    //觀察"hello"字符串與"213helldshello"是否匹配
    string dStr = "213helldshehello";
    string keyStr = "hello";
    for (decltype(dStr.size()) i = 0; i < (dStr.size() - keyStr.size()); ++i) {  //從第一個(gè)字符開(kāi)始匹配,如果不成功就接著匹配第二個(gè)字符,以此類(lèi)推
        for (auto j = i; j < (keyStr.size() + i); ++j) { //開(kāi)始匹配字符
            if (dStr.at(j) != keyStr.at(j-i)) { //如果不匹配,就終止當(dāng)前循環(huán)
                break;
            }
            if (j == (keyStr.size() + i - 1)){ //如果最后一個(gè)字符也匹配成功,就輸出匹配成功
                cout << "匹配成功" << endl;
                return 0;
            }
        }
    }
    cerr << "匹配失敗";
    return -1;
}

小結(jié):這種最基本的匹配思路是大家能想到的思路上最簡(jiǎn)單,最直接的方法.只不過(guò)我們可以發(fā)現(xiàn)他好麻煩吶,每次都要重頭匹配.然后就有人琢磨優(yōu)化,然后我們?nèi)缃窬湍艿玫絼e人的研究成果--kmp.

簡(jiǎn)單介紹: kmp算法是一種平移算法(沃漬基取的名字).他把之前匹配的信息保留下來(lái),當(dāng)此次匹配失敗后,下一次不從下一個(gè)重新匹配,而是根據(jù)前面的匹配信息選擇平移一段距離來(lái)匹配,具體平移多長(zhǎng)的距離,由getNext()方法來(lái)決定.所以接下來(lái)我們要討論到底要移動(dòng)多長(zhǎng)合適

觀察"hello"字符串與"213helldshello"是否匹配
213helldshello
   hello
我們可以發(fā)現(xiàn)到這里的時(shí)候,只有前4位匹配成功,
根據(jù)之前所說(shuō)的平移,那我們要決定平移多少合適
這么一看,我們完全可以平移4位接著匹配.
但是就會(huì)有人開(kāi)始舉反例,比如
ssssshesss   --字符串
ssssh        --匹配字符串
這個(gè)時(shí)候我們同樣發(fā)現(xiàn)前4個(gè)是匹配的,
然后我們發(fā)現(xiàn)需要平移多少合適呢?
是不是平移1位就能匹配到啦.

這個(gè)就麻煩了,我們完全不知道什么時(shí)候移多點(diǎn),什么時(shí)候移少點(diǎn).這個(gè)時(shí)候需要引入一個(gè)概念

覆蓋函數(shù)

我們觀察匹配到的字符串,即如上面的ssssh,他匹配到ssss時(shí)發(fā)現(xiàn)剩下的h不匹配,此時(shí)他的最大匹配串就是ssss.然后我們觀察他的首尾有最多幾個(gè)一樣的字符串.
比如
aba 首位的a和末尾的a相同 所以最大公共的就是1
asdasc 這種字符串找不到首位匹配的,所以為0.
asdas 首位的as 相同 所以最大公共的就是2.
這種做法有什么意義呢,當(dāng)我們發(fā)現(xiàn)字符串的長(zhǎng)度是n的時(shí)候,如果他的公共前后綴(就是前面首位相同的字符串)長(zhǎng)度為0,那么我們就平移他的長(zhǎng)度n.

比如     asdjsdjassda
        asdjas
開(kāi)始匹配時(shí),發(fā)現(xiàn)前4位是正好匹配的,他的公共匹配是asdj
我們發(fā)現(xiàn)他的公共前后綴長(zhǎng)度是0,
所以這個(gè)時(shí)候我們平移4位.
這個(gè)時(shí)候我們不管怎么去設(shè)計(jì)后面的數(shù)據(jù),都不會(huì)發(fā)生漏掉匹配串的現(xiàn)象.
比如這兩個(gè)字符串,如果我們匹配到了4個(gè),而且平移3位就能使其匹配,
那么我們就必須要
asdjsdjassda
   asdjas
我們發(fā)現(xiàn)如果要匹配成功,公共匹配的4個(gè)最后一位一定要改成a
即
asdasdjassda
   asdjas
這個(gè)時(shí)候我們發(fā)現(xiàn)他的最大公共前后綴為1,所以就應(yīng)該平移3位,剛好符合我們的假設(shè).
后面的數(shù)字是我設(shè)計(jì)匹配成功的,
真實(shí)案例中,只是可能存在匹配成功,
但是這種平移已經(jīng)能保證我們不會(huì)錯(cuò)過(guò)可能成功的案例

自我覺(jué)得平移的位數(shù)的原理已經(jīng)講得非常拎清了!

接下來(lái)就開(kāi)始講算法,
根據(jù)前面的原理,我們肯定是需要一個(gè)數(shù)組來(lái)保存最大匹配成功的公共字符串,然后還需要一個(gè)函數(shù)來(lái)計(jì)算這個(gè)公共字符串的最大公共前后綴好來(lái)決定平移幾位.

using namespace std;
int main()
{
    /*
     目標(biāo)字符串:asabusakswwlsaksaksawlsdkiis
     匹配字符串:saksawl
     */
    string deStr("asabusakswwlsaksaksawlsdkiis");
    string keyStr("saksawl");
    //1.先匹配,找到匹配到的最大字符串,需要一個(gè)字符串maxStr來(lái)保存
    string maxStr("");
    unsigned long steps;
    int length; //用于循環(huán)中計(jì)算當(dāng)前長(zhǎng)度
    //2.開(kāi)始匹配
    for (int i = 0; i < (deStr.size() - keyStr.size());) {
        length = 0;//每次重新搜索都把length置0
        steps = 1;//每次平移一段距離都重新計(jì)算平移的距離
        for (int j = i; j < (keyStr.size() + i); ++j) {
            if (deStr.at(j) != keyStr.at(j-i)) {
                if ( length > 1) {
                    maxStr = keyStr.substr(0,length);
                    //***************
                    steps = getNext(maxStr); //這里需要一個(gè)函數(shù),來(lái)告訴我們每次需要跳過(guò)多少次
                    //***************
                }
                break;  //如果當(dāng)前循環(huán)不一致則結(jié)束循環(huán)
            }
            ++length; //匹配成功字符串長(zhǎng)度加1
            if (length == keyStr.size()){
                cout << "匹配成功" << endl;
                return 0;
            }
        }
        i += steps;
    }
    cerr << "匹配不成功";
    return -1;
}

我們可以看到,上面還有一個(gè)關(guān)鍵的函數(shù),getNext(maxStr)還沒(méi)有實(shí)現(xiàn),這個(gè)函數(shù)告訴我們每次需要平移多少位.我已經(jīng)用星號(hào)標(biāo)出來(lái)啦.

接下來(lái)重中之重,俺們?cè)趺磳?shí)現(xiàn)這個(gè)函數(shù)getNext(maxStr)

unsigned long getNext(string maxStr){
    string::size_type length = maxStr.size();//存放字符串的長(zhǎng)度
    string str1;
    string str2;
    int subLen = 0;
    for (int i = 1 ; i < length; ++i) {//截取兩段字符串
        str1 = maxStr.substr(0,i);
        str2 = maxStr.substr(length-i,length);
        if(str2 == str1){//比較
            subLen = i;
        }
    }
    return length - subLen;
}

這個(gè)可能跟網(wǎng)絡(luò)上的版本有些不同,因?yàn)榇a都是基于我前面的理解,這些當(dāng)然可以優(yōu)化,但我只負(fù)責(zé)解釋清楚kmp算法到底干啥了.
最后,本文如果有些錯(cuò)誤請(qǐng)指出,我們共同進(jìn)步!