KMP字符串查找算法通過運用對這個詞在不匹配時本身就包含足夠的信息來確定下一個匹配將在哪里開始的發(fā)現(xiàn)瑟幕，從而避免重新檢查先前匹配的字符。

*此算法的核心是跳過肯定無法匹配的部分雳灾，達到高效匹配的目的播掷。 *

這里有一個可能很清晰介紹kmp的blog季二， 不過沒有代碼實現(xiàn)，也沒有講原因舀寓。

• 那么不高效的匹配是怎樣的？
  隨便搜到一個暴力匹配算法:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
/**
 * 字符串模式匹配 之 BF算法
 * Author : Yonggang Yuan
 */
#define EOS '\0' // End Of String
int main() {
    char text[] = "s a good肌蜻，Yonggang Yuan is a good student, is a good student twice ... is a good";
    char m[] = "s a good";
    int i, lenOfM = strlen(m);
    for( i=0; *(text+i) != EOS; i++ ) {
        if( memcmp(m, text+i, lenOfM) == 0 ) {
            printf("Match m at %d\n", i);
        }
    }

    return 0;
}

• 前后綴
  一個字符串 ABCABKKJSCNABCAB
  前后綴為: 1)AB 2)ABCAB
  最大前后綴為: ABCAB
• 跳過哪一部分
  移動位數(shù) = 已匹配的字符數(shù) - 對應的部分匹配值
  部分匹配值就是最大前后綴
  下面有兩個字符串

|串b |A|B|C|A|B|D|F|
|---|-|-|-|-|-|-|-|-|
|j|0|1|2|3|4|5|6|7|8|9|10|11|12|13|14|15|

在a[i=5],b[j=5]時候失配,按照kmp算法互墓，下一步就應該串b就應該向右移動（已匹配數(shù)-最大前后綴）,用代碼表示就應該為i不變，j=next[j-1]蒋搜。
怎么理解j=next[j-1]?
next是字符串b的最大前后綴大小值組成的數(shù)組,比如子串b[0~5]的最大前后綴為AB,值也就為2,所以next[4]=2篡撵。而j=next[j-1]就表示j的下標變?yōu)閎[j]前面的字符串的最大前后綴,

上面這個例子可以用下圖表示

從i[5],j[2]開始重新匹配,相對于暴力匹配法跳過i[1_2],由于i[34]與j[0~1]必然相等,也被忽略。

為什么i[1~2]可以直接跳過,會不會從i[1],j[0]開始直接匹配上了齿诞，那我來看看這情況酸休，如下圖

因為在i[5],j[5]處失配,所以i[5]應該和什么匹配未知，已知的條件不能判斷祷杈，而用已知條件只要證明i[1_4]與j[03]絕對不匹配就行了斑司，
已知條件:
1)i[0_4]與j[04]已經(jīng)匹配上了
2)next數(shù)組(看做已知的,后面在詳細求解)
如果上圖的情況能匹配上，那么i[1_4]=j[03],又已知i[1_4]=j[14],所以j[0_3]=j[14]所以j[0_3]和j[14]是j[0_{4]的前后綴,然而ABCAB的最大前后綴是AB值為2,已經(jīng)矛盾了但汞，所以i[1}4]與1[0~3]絕對不匹配宿刮，可以跳過。

• next數(shù)組
  next[k]也就是字符串b[0~k]的最大前后綴私蕾，數(shù)組求法有點像數(shù)學歸納法僵缺，首先我們知道next[0]=0,然后遞歸求取next[1],next[2]...next[n]。
  一步步來看,先判斷b[1]和b[0]是不是相等踩叭，如果相等那b[0],b[1]就為b[0~1]的前后綴

• golang代碼實現(xiàn)

func KmpMatch(astring string, bstring string) int {
        i, j := 1, 0
        next := make([]int, len(bstring))
        next[0] = 0
        for i < len(bstring) {
                if bstring[i] == bstring[j] {
                        next[i] = j + 1
                        i++
                        j++
                } else if j == 0 {
                        next[i] = 0
                        i++
                } else {
                        j = next[j]
                }
        }
        i, j = 0, 0
        for i < len(astring) {
                if astring[i] == bstring[j] {
                        if j == len(bstring)-1 {
                                return i
                        }
                        i++
                        j++
                } else {
                        if j > 0 {
                                j = next[j-1]
                        } else {
                                j = 0
                                i++
                        }
                }
        }
        return 0
}