图解kmp算法-通俗易懂kmp算法

2019-10-18 本文已影响0人 MrBryan

最近研究了一下kmp算法(Knuth-Morris-Pratt)，百度了好多帖子，看的稀里糊涂。为了自己可以简单理解(还有最重要的next数组)，也为了自己以后忘记的话不用再满世界百度，索性将自己的理解记录下来

用途

KMP算法，具体谁发明的就不说了，它主要的用途就是查找字符串，查找字符串"ab"(目标字符串)在字符串"abc"(待查找字符串)中出现的位置。换句话说，就是查找字符串"abc"是否包含字符串"ab"，如果包含，返回包含的起始位置
如下两个字符串：

str = "dabxabxababxabwabxad" (待查找字符串)
ptr = "abxabwabxad" (目标字符串)

需要计算str中是否含有ptr，如果有，返回str中出现的起始位置，如果没有，返回-1
通过肉眼观察我们发现，str中是包含ptr的
dabxabxababxabwabxad，ptr是在str中第9位(下标从0开始)开始出现的，那么返回的结果就是9

实现

先看一下go的实现代码(只是为了方便才用go实现，使用map生成的next数组效率很低)

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数组
2、匹配ptr和str，当ptr失配时，利用next数组，实现ptr的最大后移，从而避免不必要的匹配，减少匹配次数
by smoke_zl

计算next数组

前缀和后缀公共部分的最大长度

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

next数组

next数组是ptr每一位及之前的字符串中，前缀和后缀公共部分的最大长度的集合
比如ptr字符串的长度是11(abxabwabxad)，那么next数组就有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函数是如何计算next数组的值的

image

上图第一行，左边i值为ptr下标的值，中间是ptr字符串的每一位，右边是对应的next[i]值，从 i = 0 开始，分析每一行的计算过程

i = 0
由于字符串的前一位只有一个字符，是没有前后缀的，所以next[0] = 0，对应代码

k := 0
next[0] = k

i = 1
从上一次循环，可知 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]的判断，执行k++，这时 k = 1，最后next[i] = k，也就是next[3] = 1
i= 4
k = 1, 满足findStr[k] == findStr[i]的判断，执行k++，这时 k = 2，最后next[i] = k，也就是next[4] = 2
i = 5
k = 2，满足 k > 0 && findStr[k] != findStr[i]，执行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 的逻辑和上边相似，就不重复说了，可以参照着图看
i = 10
k = 4，满足 k > 0 && findStr[k] != findStr[i]，执行k = next[k-1]，在这里仔细说下k = next[k-1]的意思
当 i = 9 执行完后，字符串指针为下图的样子，此时前后缀公共部分的最大字符串为abxa
image
再看abxa字符串，abxa字符串的前后缀公共部分的最大字符串为a，所以 i = 9 时，前后缀公共部分可以分解为下图的形式
image
所以当 i = 10 时，如果k > 0 && findStr[k] != findStr[i]，也就是 k指向的b不等于i指向的d，如图
image
那么k指针就会执行k = next[k-1]回到前缀的公共前缀继续比较，也就是
image
这样，就保证最效率的匹配

匹配字符串

第一部分利用next函数得到了next数组，下一步执行kmp函数，对ptr和str进行匹配，并当ptr和str失配时，利用next数组，进行最大位移，由于kmp函数和next函数差不多，这里就不详细讲了，直接上图