本文適合以前學(xué)過KMP算法、想要溫習(xí)和加深理解的讀者閱讀，不適合作為初學(xué)材料。

傳統(tǒng)的字符串匹配算法

在傳統(tǒng)的字符串匹配算法中，不論主字符串（T）和模式串（P，亦即關(guān)鍵字）已經(jīng)匹配了多少位字符，只要T[i]和P[j]不相符，就得回爐重造倒回重新匹配，j和i都需要回溯。

但事實(shí)上，在T和P逐步匹配的過程中，我們完全可以得到一些有效的、可以避免重復(fù)工作的數(shù)據(jù)——

KMP

比如T的前5位和P的前5位已經(jīng)匹配成功，在第6位時(shí)匹配失敗，那么如果說在P的前5位（假設(shè)是ABCAB）里，有一個(gè)k值，使前k位和后k位的字符串可以相匹配（在這個(gè)例子里，k=2，前2位和后2位的字符串都是AB），則在 “T的前5位和P的前5位已經(jīng)匹配成功” 的前提下，我們就可以不移動(dòng)i，并且不必將j重設(shè)為0，而使j=k（指向k位字符串后的第一位，在這個(gè)例子中，即指向‘C’）。
這也就是KMP算法的核心思想。

注意，這里保持了i始終不回溯，但最終要求的結(jié)果（字符串P在T中首先出現(xiàn)的位置）是i-j。也就是說，如果單獨(dú)把結(jié)果res當(dāng)做一個(gè)變量的話，res是可能會(huì)回溯的。

于是KMP算法可以概括為：
不回溯T的i指針，在i和j不匹配的情況下將j重設(shè)為k。 k值由進(jìn)行匹配之前對(duì)P字符串的計(jì)算得到，存儲(chǔ)在數(shù)組next[p.length()]里。

代碼

    #include<iostream>
    #include<string>
    using namespace std;
    int* GetNext(const string& p){

        int lenp = p.length();
       int*res = new int[lenp];

        int k = 0;
        *(res+0) = 0; 
        if (lenp > 1)*(res+1) = 0;

        for (int i = 1; i < lenp-1; i++){
            if (p[i] == p[k])*(res+i+1) = ++k;
            else {
                *(res+i+1)= 0;
                k = 0;
            }
        }
        return res;
    }

    void FindPosition(const string& t,const string& p){
        int pos;
        int lent = t.length();
        int lenp = p.length();
        int* next = new int[lenp];

        next = GetNext(p);
        //get ks

        bool suc = false;
        int j = 0;
        for (int i = 0; i < lent; ){
            if (t[i] == p[j]){ 
                if (j == lenp - 1){
                    suc = true;
                    pos = i-j+1;
                    break;
                }
                else{
                        i++; j++;
                }
            }
            else{
                if (j == 0)i++;
                else  j = next[j];
            }
        }

        //print result
        if (suc){
            cout << p << " is found at position " << pos << endl;
        }
        else{
            cout << "Not found." << endl;
        }
   }

    int main(){
        string t, p;
        cin >> t >> p;
        FindPosition(t, p);
        system("pause");
          return 0;
      }

這是我擼的渣代碼，和教科書上簡(jiǎn)潔而優(yōu)美的代碼當(dāng)然有云泥之別，甚至可能還有bug。
但就基本思路而言，與這段代碼的冗長(zhǎng)所共生的直白邏輯也許更讓人易于理解，故在此貼上，聊作對(duì)前文不走心的解釋的補(bǔ)償。

最后再附上簡(jiǎn)潔而優(yōu)美的教科書代碼。

public static int[] getNext(String ps) {

char[] p = ps.toCharArray();

int[] next = new int[p.length];

next[0] = -1;

int j = 0;

int k = -1;

while (j < p.length - 1) {

   if (k == -1 || p[j] == p[k]) {

       next[++j] = ++k;

   } else {

       k = next[k];

   }

}

return next;

}