KMP算法详解

KMP算法详解

一直都没弄明白，也没下决心去弄明白。昨天感觉基本上差不多了，整理一下，再加深一下印象。

问题

给你两个字符串 haystack和 needle，请你在 haystack字符串中找出 needle字符串的第一个匹配项的下标（下标从 0开始）。如果 needle不是 haystack的一部分，则返回 -1 。

AC代码：

func strStr(haystack string, needle string) int {
    needlelen := len(needle)
    haystacklen := len(haystack)
    next := make([]int,needlelen)
    next[0] = 0
    j := 0
    for i:=1;i<needlelen;i++{
        for j > 0 && needle[i] != needle[j]{
            j = next[j-1]
        }
        if needle[i] == needle[j]{
            j++
        }
        next[i] = j
    }
    j = 0
    for i:=0;i<haystacklen;i++{
        for j > 0 && needle[j] != haystack[i]{
            j = next[j-1]
        }
        if needle[j] == haystack[i]{
            j++
        }
        if j == needlelen{
            return i-j+1;
        }
    }
    return -1
}

简介

判断一个字符串（模式串）是不是另外一个字符串（文本串）的子串，怎么做？

最容易想到的：暴力匹配。

比如有下面的两个字符串：

abacac和 ac

开始肯定是第一个 a开始和 ac进行匹配，匹配失败了，然后从 b再开始匹配。最坏情况，每一个都要判断到匹配字符串的最后一个字符，两层循环，时间复杂度很容易想到就是。

但是事实上，如果从人工匹配的角度来看，我们都知道 b不可能匹配成功，让你用肉眼匹配，傻子才会去看 b。但是计算机程序为了全部判断还是要去尝试一下。

那么怎么把这种无效的匹配让开呢？直观上可能想到，我判断第一个能不能匹配上不就行了，应该能降低时间复杂度？

那么再举一个例子：aaaaaaaaaa和 ab，时间复杂度一样是。

所以不仅仅要看第一个，看第一个也无法完全抹去无效的匹配。这时候需要一种高效的匹配算法，核心思想就是在匹配的过程中要记录，匹配失败后从第一个可能成功的地方开始即可，不要做无效工作。

因此就有了超难理解的KMP算法以及各种比KMP还要复杂的算法。这里就先好好的讲一下KMP，希望以后可以真正理解，抬手就来。

概念

前缀表：记录下标 i之前（包括 i）的字符串中，有多大长度的相同前缀后缀。

前缀是指不包含最后一个字符的所有以第一个字符开头的连续子串 。

后缀是指不包含第一个字符的所有以最后一个字符结尾的连续子串 。

啥意思？举例子就好了

模式串下标	0	1	2	3	4	5	6	7	8	9	10	11	12
字符串	a	b	c	d	a	b	c	a	b	c	d	a	b
前缀表	0	0	0	0	1	2	3	1	2	3	4	5	6

怎么算的？

下标为 0，字符串为 a，前缀为空（因为不包含最后一个字符，因此字符就没了），后缀为空（因为不包含第一个字符，因此字符就没了），因此相同前缀后缀长度为0（因为都是空串）

下标为 1，字符串为 ab，前缀为 a，后缀为 b，因此相同前缀后缀长度为 0

下标为 2，字符串为 abc，前缀为 ab，后缀为 bc，因此相同前缀后缀长度为 0

下标为 3，字符串为 abcd，前缀为 abc，后缀为 bcd，因此相同前缀后缀长度为 0

下标为 4，字符串为 abcda，前缀为 abcd，后缀为 bcda，因此相同前缀后缀长度为 1，也就是 a

下标为 5，字符串为 abcdab，前缀为 abcda，后缀为 bcdab，因此相同前缀后缀长度为 2，也就是 ab

下标为 6，字符串为 abcdabc，前缀为 abcdab，后缀为 bcdabc，因此相同前缀后缀长度为 3，也就是 abc

下标为 7，字符串为 abcdabca，前缀为 abcdabc，后缀为 bcdabca，因此相同前缀后缀长度为 1，也就是 a

…

下标为 12，字符串为 abcdabcabcdab，前缀为 abcdabcabcda，后缀为 bcdabcabcdab，因此相同前缀后缀长度为 6，也就是 abcdab

人工计算还是挺好算的，用眼睛看看简单算算就行了。网上有些资料是从 -1开始，然后右移一位，我认为不好理解，不如保留前缀表的本意

所以算来算去，前缀表有什么用处呢？

前缀表可以帮助我们在匹配不成功的时候找到前面最佳的重新开始的位置，从而保证我们只遍历文本串一次就能判断模式串与文本串是否匹配。（废话）

先举例：后面的 i指文本串的下标，j指模式串的下标。（文本串下标保证递增，绝对不回退）

文本串下标	0	1	2	3	4	5
字符串	a	c	b	a	b	a

模式串下标	0	1	2	3	4
字符串	a	c	b	a	c
前缀表	0	0	0	1	2

开始匹配，i和 j匹配的很顺利，转眼就到了 i=j=4，然后发现糟了，匹配不上了，现在 j要回退，找到重新开始匹配的位置。

j退到哪里呢？因为 j是没有匹配上的，而 j-1如果有意义（j≠0），一定是能匹配上的！（为什么？因为只有匹配上了 j才会移动，j移动过的位置一定是之前匹配好了的）

那么 j-1是匹配上的又说明了什么呢？说明对于 0~j-1的字符串，如果有相同的前缀后缀，一定也是能和i-1匹配的上的，因此就不需要回退超过前缀的位置！

还是上面的例子，模式串的 j-1前缀表的值是 1，说明 j-1位置的 a在模式串的前面也出现过，就是模式串 0位置的 a。由于 j-1是和 i-1匹配上了的，因此 j=0和 i-1也是匹配上了的，不需要再去看模式串 0的位置，只需要看0的后一个位置 1和 i是否能匹配上就好了！

流程步骤：

1. i和 j匹配不上了，隐含条件是 i-1和 j-1是可以匹配的
2. 看一下 j-1后缀的相同长度的前缀长度，也就是 next[j-1]的值
3. 回退 j到 next[j-1]的位置，隐含了这一步将相同长度的前缀绕过

然后 j=next[j-1]后就去判断 j和 i是不是相同就好了，很不幸的是，还是不相同，i指向的是 b，j指向的是 c。

那么没办法，留着这个前缀也无法匹配了，只好再次回退，这一退就退到 j=0了，但是还是不相等。

j=0就没有办法再次回退了，只好 i++，舍弃这一个部分的文本串，开始新的文本串。

到这里应该明白了前缀表的作用了，字面上很难理解，跟着流程走一遍就明白它的思想了，确实精妙

字符串匹配

所以在已知 next数组的前提下，这个字符串匹配的代码就很简单了。虽然简单，但是结构一点都不可以修改，循环和顺序都是精心设计的。

j = 0
for i:=0;i<haystacklen;i++{
    for j > 0 && needle[j] != haystack[i]{ // 匹配不上就一直回退，j=0说明真的匹配不上了，跳出来i++
        j = next[j-1]
    }
    // j=0也会跳到这里尝试一下
    if needle[j] == haystack[i]{ // 匹配上的就能j++去看模式串的下一个字符了，然后进入下一个循环i++，判断文本串的下一个字符能不能和模式串的这个字符匹配上
        j++
    }
}

还有一个问题，next数组怎么求？

next数组

首先要明确一点，next数组是针对模式串而言的，与文本串半毛钱关系没有

模式串下标	0	1	2	3	4	5	6
字符串	a	b	a	a	b	a	e
前缀表	0	0	1	1	2	3	0

其实思想和匹配是相同的，不同的地方在于上面的是用模式串和文本串进行匹配，这里是用自己和自己进行匹配，匹配的过程中看看能匹配上多少，就能得出 next数组的数值了

next[0]=0，初始化毫无争议，因为空串一定是0

指针 i同样一直向前，指针 j会进行回退，因为 next[0]确定了，因此直接初始化i=1

最开始，j指向的是 0的位置，就在这里等着到底哪个 i能和我这个可爱的 j匹配上

到了 i=2，匹配上了！这时候 j不满足了，是不是 i+1也能和 j+1匹配上呢？所以就 j++，尝试匹配下一个

要是匹配不上了怎么办呢？比如 j=3,i=6匹配不上了，也隐含了条件，就是 j=2是能和 i-1匹配上的（要是匹配不上j也不可能不等于0）

那么j=2时候的相同长度的前后缀在哪里呢？因为如果相同也不需要去看了，所以更新j=next[j-1]就可以了，和上面的字符串的匹配思想是完全相同的。

如果还是匹配不上，那么j只好乖乖变为0，等待着下一个能匹配上的将j+1了

代码如下：

next[0] = 0 // 初始化
j := 0 // j指向首位
for i:=1;i<needlelen;i++{ // 遍历模式串，不回退
    for j > 0 && needle[i] != needle[j]{
        j = next[j-1] // 匹配不上了，绕过已知的相同长度的前后缀，直到变为j=0的初始状态
    }
    // 如果j=0还是有一次判断的机会的
    if needle[i] == needle[j]{ // 匹配上了将j解放出来，+1再试试
        j++
    }
    next[i] = j // 赋值next数组
}

时间复杂度分析

设 n为文本串长度，m为模式串长度

在匹配的过程中，根据前缀表不断调整匹配的位置，如果没有一个字符能匹配的上，时间复杂度就是文本串的指针从头移到尾，也就是

如果能匹配上一些字符，回退的次数也不可能超过 n次。因此时间复杂度是

生成 next数组，不会比匹配的时间复杂度高（因为如果模式串比文本串还要长，根本就不需要匹配了）

所以从平方级别的时间复杂度直接降到了线性的时间复杂度。

总结

看过很多遍，应该也曾经懂过，就是从来没有整理过，因此可能也没有真正懂过。

希望这次能真真正正懂了，后面忘记了再来看看这篇文章，希望能快一些想起来。