简介

KMP 算法是一种改进的字符串匹配算法，由 D.E.Knuth，J.H.Morris 和 V.R.Pratt 提出的，因此人们称它为克努特 — 莫里斯 — 普拉特操作（简称 KMP 算法）。KMP 算法的核心是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是通过一个 next () 函数实现，函数本身包含了模式串的局部匹配信息。KMP 算法的时间复杂度O(m + n)。

也就是说，KMP 算法是用来解决字符串匹配问题的，从一个主字符串 text 中寻找一个子字符串 (模式字符串)pattern，看这个子串是否在主串中，比如对于 text=’abaacababcac’ 和 pattern=’ababc’，子串是包含在主串中的，同时它在主串中的索引是 5。

KMP 算法原理

KMP 算法则用了一种聪明的办法，当发现字符串不匹配的时候，并不会从头开始比较，因为之前已经匹配成功的字符可以给我们提供一些有用的信息，利用这个信息我们可以将子串移动到某个位置，并从这个位置直接开始比较，它的时间复杂度降到了 O(m+n)，也就是 2 个字符串的长度之和。

网上有很多关于 KMP 的代码，大体知道是通过计算子串（模式串）自身来获得一个 next 数组，然后在匹配过程中通过 next 数组来决定下一个匹配位置，代码虽然不复杂，然而知其然不知其所以然，如果不明白其中原理，那么很难将这个算法写出来。

本文将介绍一种最朴素的 KMP 算法，目的就在于彻底搞懂 KMP 算法原理，它的 next 是怎么来的，以及算法是如何奏效的。

字符串的前缀和后缀

首先我们需要知道字符串的前缀和后缀：
对于字符串 ababc 来说，它的前缀有 [a,ab,aba,abab]，也就是以字符串第一个字符作为开头，同时不包括最后一个字符的所有子串，同理它的后缀有 [c,bc,abc,babc]，也就是以字符串最后一个字符作为结尾，同时不包括第一个字符的所有字串。

字符串的最长公共前后缀

了解了这个，我们再来说什么是字符串的最长公共前后缀，说白了，也就是前缀和后缀这 2 个集合中的相同部分，同时取最长的那个，就是这个字符串的最长公共前后缀。显然，在这个例子中，ababc 是没有公共前后缀的。但是对于 abab，它的前缀和后缀分别是 [a,ab,aba] 和 [b,ab,bab]，那么它的最长公共前后缀就是 ab。

现在，我们的目标就是取得 ababc 所有子串 [a,ab,aba,abab,ababc] 的最长公共前后缀的长度，分别保存在 next 数组中，我们只要知道最大长度即可，并不用关心串具体是什么，而我们目前通过观察即可得出 next 数组这里是 [0,0,1,2,0]，我们先知道这个结果即可，此计算方法后续会说明。

KMP 的思路分析

得到这个有什么用，回到刚刚的例子，当我们第一次碰到不匹配时（i 和 j 都等于 3 的时候）：

此时 i 和 j 之前的 3 个字符 aba 必然完全匹配的，因为只有前面匹配成功了 j 才能走到 3，而我们又知道 aba 的最长公共前后缀是 a，这可以给我们一个很好的提示，主串中的 aba 的后缀和字串中的 aba 前缀有最长的公共部分 a，这样一来，我们就没必要重新比较了，直接将相同部分对齐就好了，也就是说让 j 退回到位置 1 就可以了，而 i 保持不变。

分析一下，为什么 j 知道应该退回到位置 1：

1. 我们知道 j 是在位置 3 不匹配的，那么 j 前面的字符串我们可以知道是 aba
2. 前面我们已经得到了 next 数组，知道 aba 的最长公共前后缀长度是 1
3. 也就是说，我们可以知道 i 之前 1 个位置（主串的后缀）和子串开头之后 1 个位置（子串的前缀）是相同的
4. 进而我们可以让相同部分对齐，也就是让 j=next[j-1]

接下来，我们发现 i 和 j 仍然不匹配，而 j 之前的字符 a 最长公共前后缀是 0，此时 j 退到位置 0，i 仍然保持不变。

i 和 j 匹配，同时右移一格

此时 i 和 j 不匹配，j=next[j-1] 回退到 0，然后我们发现 i 和 j 仍然不匹配，同时 j 已经是 0 了，那么我们就让 i 往右移动一格。

可以看到，相比于暴力解法，i 始终在前进，并没有后退（顶多保持不变），然后我们通过 next 数组来改变 j 的值。

def strStr(self, text: str, patten: str) -> int:
    next=KMP(patten)       #获取next数组
    n1,n2=len(text),len(patten)
    if n2==0:
        return 0
    i,j=0,0
    while i<n1:
        if text[i]==patten[j]:
            i+=1
            j+=1
        else:
            if j>0:
                j=next[j-1]
            else:
                i+=1
        if j==n2:
            return i-n2
    return -1

求解字符串最长公共前后缀

最后，我们还剩下一个问题，如何求 next 数组，也就是求模式字符串各个子串的最长公共前后缀长度。
我们先初始化一个和模式字符串长度相等的 next 数组，在 next 数组中，第 1 位默认为 0，因为我们规定只有一个字符的字符串没有前缀和后缀，自然公共前后缀长度只能是 0。
我们依然设定 2 个指针 i 和 j，j 指向位置 0，i 从位置 1 开始依次为 next 数组进行赋值

我们可以把这个过程依然看作是 2 个字符串的比较，j 指向的是模式字符串的前缀，而 i 指向的是模式字符串的后缀

和上面的字符串匹配一样，我们执行同样的处理：

1. 当 i 和 j 匹配时，i 和 j 同时右移一格
2. 当 i 和 j 不匹配时，如果 j 不在字符串开头（位置 0），就回退到上一个能匹配到的位置
3. 当 i 和 j 不匹配时，如果 j 在字符串开头（位置 0），那么 i 就右移一格

对 next [1] 赋值：i 和 j 不匹配，同时 j 已经是字符串开头，赋值 0

对 next [2] 赋值，i 和 j 匹配，此时 j 为 0，代表只有 1 个字符匹配 (j+1)，赋值 1

对 next [3] 赋值，i 和 j 匹配，此时 j 为 1，代表有 2 个字符匹配 (j+1)，赋值 2

对 next [4] 赋值，i 和 j 不匹配，此时 j 为 2，可以得知 j 前面的字符是 ab，而 ab 的最长公共前后缀长度就是 next[1]，这个值我们前面已经求得了结果是 0，所以 j 回退到位置 0，用代码表示就是 j=next[j-1]

此时 i 和 j 仍然不匹配，但是 j 已为 0，无法继续回退，所以直接对 next [4] 赋值为 0

实际上，我们在求解模式字符串 ababc 的最长公共前后缀长度的时候，不可避免的会对它的子串进行求解，这样可以方便在不匹配时进行回退，这也是动态规划的思想，要求的结果可以用先前已经求得的结果得出。而我们本身就是要对模式字符串的各个子串进行求解，所以可谓一举两得。

def KMP(patten):
    if not patten:
        return []
    n=len(patten)
    next=[0]*n
    i,j=1,0
    while i<n:
        if patten[i]==patten[j]:
            next[i]=j+1
            i+=1
            j+=1
        else:
            if j>0:
                j=next[j-1]
            else:
                next[i]=0
                i+=1
    return next

对比一下上一段的字符串匹配代码，可以发现，2 段代码的执行逻辑几乎一模一样，不同之处只是我们在比较过程中插入了对 next 数组进行赋值的代码。

可以这样理解，在字符串匹配中，i 指向的是主串，j 指向的子串，比较的是主串和子串。而在求公共前后缀的时候，我们相当于把模式字符串拆成了前后两部分，同样是对这 2 部分进行字符串匹配，相当于自己比自己。

以上就是 KMP 算法的核心原理及实现，当然，实现方式并不是只有我这一种，KMP 的实现算法多种多样，包括生成的 next 数组都会不一样，而我这里的代码只是希望能够把 KMP 的思路表述清楚：

1. KMP 通过计算模式字符串自身得到 next 数组；
2. 不匹配时通过 next 数组信息进行回退，而不用再从头开始比较；
3. 原理就是利用模式字符串的公共前后缀信息，所以算法是奏效的。