国内精品91视频在线,久久香蕉精品国产亚洲

最近研究了一下kmp算法(Knuth-Morris-Pratt)，百度了好多帖子，看的稀里糊涂。為了自己可以簡單理解(還有最重要的next數(shù)組)，也為了自己以后忘記的話不用再滿世界百度，索性將自己的理解記錄下來

用途

KMP算法，具體誰發(fā)明的就不說了，它主要的用途就是查找字符串，查找字符串"ab"(目標(biāo)字符串)在字符串"abc"(待查找字符串)中出現(xiàn)的位置。換句話說，就是查找字符串"abc"是否包含字符串"ab"，如果包含，返回包含的起始位置
如下兩個字符串：

str = "dabxabxababxabwabxad" (待查找字符串)
ptr = "abxabwabxad" (目標(biāo)字符串)

需要計算str中是否含有ptr，如果有，返回str中出現(xiàn)的起始位置，如果沒有，返回-1
通過肉眼觀察我們發(fā)現(xiàn)，str中是包含ptr的
dabxabxababxabwabxad，ptr是在str中第9位(下標(biāo)從0開始)開始出現(xiàn)的，那么返回的結(jié)果就是9

實現(xiàn)

先看一下go的實現(xiàn)代碼(只是為了方便才用go實現(xiàn)，使用map生成的next數(shù)組效率很低)

func main() {
    str := "dabxabxababxabwabxad"
    ptr := "abxabwabxad"
    i := kmp(str, ptr)
    fmt.Println(i)
}

func next(findStr string, num int) (next map[int]int) {
    k := 0
    next = make(map[int]int, num)
    next[0] = k
    for i := 1; i < num; i++ {
        for k > 0 && findStr[k] != findStr[i] {
            k = next[k-1]
        }
        if findStr[k] == findStr[i] {
            k++
        }
        next[i] = k
    }
    return next
}

func kmp(str string, findStr string) int {
    strL := len(str)
    findStrL := len(findStr)
    k := 0
    nextArr := next(findStr, findStrL)
    for i := 0; i < strL; i++ {
        for k > 0 && findStr[k] != str[i] {
            k = nextArr[k-1]
        }
        if findStr[k] == str[i] {
            k++
        }
        if k == findStrL {
            return i - k + 1
        }
    }
    return -1
}

算法由兩部分組成
1、計算ptr每一位及之前的字符串中，前綴和后綴公共部分的最大長度的next數(shù)組
2、匹配ptr和str，當(dāng)ptr失配時，利用next數(shù)組，實現(xiàn)ptr的最大后移，從而避免不必要的匹配，減少匹配次數(shù)
by smoke_zl

計算next數(shù)組

前綴和后綴公共部分的最大長度

一個字符串ababa，他的前綴是可以是a,ab,aba,abab(不包含最后一位)，后綴是a,ba,aba,baba(不包含第一位)
前綴后綴公共部分就是a和aba，公共部分最大就是aba，公共部分的最大長度就是3

next數(shù)組

next數(shù)組是ptr每一位及之前的字符串中，前綴和后綴公共部分的最大長度的集合
比如ptr字符串的長度是11(abxabwabxad)，那么next數(shù)組就有11個元素

next[0]表示ptr前一位a中，前綴和后綴公共部分的最大長度，由于a中沒有前綴和后綴，所以next[0]=0
next[1]表示ptr前兩位ab中，前綴和后綴公共部分的最大長度，ab的前綴是a，后綴是b，沒有公共部分，所以next[1]=0
同理
next[2]=0(abx中無公共前后綴)
next[3]=1(abxa公共前后綴最長為a，長度為1)
next[4]=2(abxab公共前后綴最長為ab，長度為2)
next[5]=0(abxabw中無公共前后綴)
next[6]=1(abxabwa公共前后綴最長為a，長度為1)
next[7]=2(abxabwab公共前后綴最長為ab，長度為2)
next[8]=3(abxabwabx公共前后綴最長為abx，長度為3)
next[9]=4(abxabwabxa公共前后綴最長為abxa，長度為4)
next[10]=0(abxabwabxad中無公共前后綴)

下面用圖文來解釋，next函數(shù)是如何計算next數(shù)組的值的

kmp.png

上圖第一行，左邊i值為ptr下標(biāo)的值，中間是ptr字符串的每一位，右邊是對應(yīng)的next[i]值，從 i = 0 開始，分析每一行的計算過程

i = 0
由于字符串的前一位只有一個字符，是沒有前后綴的，所以next[0] = 0，對應(yīng)代碼

k := 0
next[0] = k

i = 1
從上一次循環(huán)，可知 k = 0，既不滿足代碼中 k > 0 && findStr[k] != findStr[i]的判斷，也不滿足 findStr[k] == findStr[i]的判斷，所以最后next[i] = k，也就是next[1] = 0
i = 2
同上，k = 0，next[2] = 0
i = 3
k = 0，滿足findStr[k] == findStr[i]的判斷，執(zhí)行k++，這時 k = 1，最后next[i] = k，也就是next[3] = 1
i= 4
k = 1, 滿足findStr[k] == findStr[i]的判斷，執(zhí)行k++，這時 k = 2，最后next[i] = k，也就是next[4] = 2
i = 5
k = 2，滿足 k > 0 && findStr[k] != findStr[i]，執(zhí)行k = next[k-1]，k = next[2-1] = next[1] = 0
很多人（包括我）都很不理解k = next[k-1]這行代碼的意思，這里先不做解釋，后邊 i = 10 的時候說
i = 6...i = 9
i = 6 到 i = 9 的邏輯和上邊相似，就不重復(fù)說了，可以參照著圖看
i = 10
k = 4，滿足 k > 0 && findStr[k] != findStr[i]，執(zhí)行k = next[k-1]，在這里仔細說下k = next[k-1]的意思
當(dāng) i = 9 執(zhí)行完后，字符串指針為下圖的樣子，此時前后綴公共部分的最大字符串為abxa

kmp1.png

再看abxa字符串，abxa字符串的前后綴公共部分的最大字符串為a，所以 i = 9 時，前后綴公共部分可以分解為下圖的形式

kmp2.png

所以當(dāng) i = 10 時，如果k > 0 && findStr[k] != findStr[i]，也就是 k指向的b不等于i指向的d，如圖

kmp3.png

那么k指針就會執(zhí)行k = next[k-1]回到前綴的公共前綴繼續(xù)比較，也就是

kmp4.png

這樣，就保證最效率的匹配