KMP算法是用來匹配字符串的誉碴，比如在字符串** haystack:ABCACEABCABDA中查詢是否存在子串 needleABCAB矢赁，這種問題可以暴力破解，即：將 haystack中所有長(zhǎng)度與needle相等的字串與needle**比較。

KMP與暴力破解的區(qū)別在于：

• 暴力破解是** haystack的子串ABCAC(_ABCACEABCABDA)與needle**ABCAB比較后芯勘，由于不匹配，接下來會(huì)用BCACE(A_BCACEABCABDA)與ABCAB比較腺逛。
• KMP相對(duì)“智能”一些荷愕，若ABCAC(_ABCACEABCABDA)與ABCAB比較不匹配后，會(huì)選ACEAB(ABC_ACEABCABDA)與needle比較，至少路翻，他們有相同的開頭狈癞。那么，如何才能正確選擇到相同開頭的字串是KMP的關(guān)鍵茂契。

在KMP中通過部分匹配表來實(shí)現(xiàn)相對(duì)智能選擇合適的開頭蝶桶。部分匹配表是對(duì)字符串needle的一種“描述”，取字符串“前綴”和后綴的最大共有長(zhǎng)度掉冶，其規(guī)則如下：

－　"A"的前綴和后綴都為空集真竖，共有元素的長(zhǎng)度為0；
－　"AB"的前綴為[A]厌小，后綴為[B]恢共，共有元素的長(zhǎng)度為0；
－　"ABC"的前綴為[A, AB]璧亚，后綴為[BC, C]讨韭，共有元素的長(zhǎng)度0；
－　"ABCA"的前綴為[A, AB, ABC]癣蟋，后綴為[BCA, CA, A]透硝，共有元素的長(zhǎng)度為，共有元素為“A”疯搅，長(zhǎng)度為1濒生；
－　"ABCAB"的前綴為[A, AB, ABC, ABCA]，后綴為[BCAB, CAB, AB, A]幔欧，共有元素為"AB"罪治，長(zhǎng)度為2；

故needle的部分匹配表為[0,0,0,1,2]礁蔗。ABCAC(_ABCACEABCABDA)與needleABCAB比較后觉义，下一次比較開始的位置為本次匹配開始的位置再向右偏移x位，其中x的值是ABCAC與ABCAB的最大匹配長(zhǎng)度4(ABCA)減去最后一個(gè)匹配的字母A在部分匹配表中`所對(duì)應(yīng)的值浴井。即：

移動(dòng)位數(shù) = 已匹配的字符數(shù) - 已匹配的最后一個(gè)字符對(duì)應(yīng)匹配值

其中的原理大概描述是：

ABCAC與ABCAB比較谁撼，其中匹配的部分是ABCA。由于最終還是不匹配滋饲，出于效率考慮厉碟，下次比較開始的位置需要盡可能靠后，那不如向右數(shù)4位吧(ABCA的長(zhǎng)度)屠缭，但這個(gè)萬一ABCA中某部分也可以作為下次比較的開頭呢箍鼓？通過“觀察”發(fā)現(xiàn)ABCA末尾的只有A可以作為下一次的開始(如果是ABAB，那么就是末尾的AB可以作為下次比較的開始)呵曹，那就向右數(shù)4-1位吧款咖。

上述過程的寫成偽代碼：

// 部分匹配表
int pi[needle長(zhǎng)度]
// pi的計(jì)算
...
// 遍歷
int i = 0, j = 0;
while (i < n) {
  if (haystack[i] == needle[j]) {
    j++;
    i++;
  } else {
    if (j > 0) {
      i = i + j - pi[j-1];
    }
    j = 0;
  }
  if (j == m) {
    return i - j;
  }
}

然而這并不是最好的方案何暮，當(dāng)haystack[i] != needle[j]的時(shí)候，改變i和j不如單獨(dú)改變j铐殃，即ABCAC(_ABCACEABCABDA)與ABCAB比較不匹配后海洼，會(huì)選ACEAB(ABC_ACEABCABDA)與needle比較，富腊，也可以理解為haystack[4] != needle[4]時(shí)坏逢，i==4不變，j=1赘被，這樣i==3就不用再比較一次了是整，而匹配表中的數(shù)據(jù)恰好可以直接給賦值給j。如下圖：

// 部分匹配表
int pi[needle長(zhǎng)度]
// pi的計(jì)算
...
// 遍歷
int i = 0, j = 0;
while (i < n) {
  if (haystack[i] == needle[j]) {
    j++;
    i++;
  } else {
    if (j == 0) {
      i++;
    } else {
      j = pi[j-1];
    }
  }
  if (j == m) {
    return i - j;
  }
}

好了民假，目前為止浮入，至少KMP的原理是知道了，下面看看KMP的標(biāo)準(zhǔn)代碼

int strStr(char* haystack, char* needle) {
    int n = strlen(haystack), m = strlen(needle);
    if (m == 0) {
        return 0;
    }
    // 部分匹配表 pi
    int pi[m];
    pi[0] = 0;
    // pi的計(jì)算
    for (int i = 1, j = 0; i < m; i++) {
        while (j > 0 && needle[i] != needle[j]) {
            j = pi[j - 1];
        }
        if (needle[i] == needle[j]) {
            j++;
        }
        pi[i] = j;
    }
    for (int i = 0, j = 0; i < n; i++) {
        while (j > 0 && haystack[i] != needle[j]) {
            j = pi[j - 1];
        }
        if (haystack[i] == needle[j]) {
            j++;
        }
        if (j == m) {
            return i - m + 1;
        }
    }
    return -1;
}

羊异？事秀？？Ｒ安啊；嗤怼！
什么鬼筒愚？pi到底是怎么計(jì)算出來的？

有以下三個(gè)思考點(diǎn)菩浙。

1. 計(jì)算過程可以看成needle與needle’（needle == needle‘）字母依次比較比較巢掺，只不過最開始是needle[i]與needle’[j], i == 1, j==0 且i > j永遠(yuǎn)成立;
2. 動(dòng)態(tài)規(guī)劃：pi[0]==0且pi[i+1] <= pi[i]+1。
3. 有限狀態(tài)自動(dòng)機(jī)：pi中所保存的劲蜻，是對(duì)應(yīng)狀態(tài)遇到不符合期望的條件將要切換到的狀態(tài)陆淀。狀態(tài)j，0 <= j <= needle的長(zhǎng)度先嬉，當(dāng)j==needle的長(zhǎng)度轧苫，檢索成功。

但暫時(shí)本人對(duì)這些依然沒有特別清晰的感受疫蔓，并以此清晰描述其中的細(xì)節(jié)含懊，待續(xù)。

參考資料：
http://www.ruanyifeng.com/blog/2013/05/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm.html

https://zhuanlan.zhihu.com/p/83334559