在复习数据结构时复习到了第五章字符串与数组，其中有一个字符串的模式匹配问题之前一直困扰着我，尤其是KMP算法。因此在这里记录一下方便自己回忆和复习，如果能对大家有所帮助那就更好啦😃

字符模式匹配一般有BF（暴力破解）和KMP两种算法（还有其他的欢迎大佬们在评论区补充🙌）。而BF之所以不被使用原因就在于其极度低下的效率（最坏的情况需要比较m*n次，m是模式串的长度，n是目标串的长度）

而KMP算法的优势就在于其对于匹配失败时的情况的处理很巧妙，目标串是不需要后退的，模式串也追求尽量往后挪。这样可以大大减少匹配的次数，那么具体是如何实现的呢？我们知道KMP算法包括求next数组和利用next数组进行字符匹配两部分，其中前者应该是最难理解的，后者相对简单，因此我们先看已知next数组的情况下KMP是如何进行字符匹配；再看如何构建next数组；并在过程中插入具体例子讲解。

（一）已知next数组利用KMP进行字符串的模式匹配

def kmp(des_str: str, format_str: str, pos: int):
    """
        KMP算法：
            用模式串匹配从指定位置开始目标字符串
            des_str:目标串
            format_str:模式串
            pos:开始匹配的位置
    """

    next_values = get_next(format_str)

    i = pos
    j = 0

    while i < len(des_str) and j < len(format_str):
        if j == -1 or des_str[i] == format_str[j]:
            i += 1
            j += 1
        else:
            j = next_values[j]

    if j == len(format_str):
        return True, i - len(format_str)
    else:
        return False, None

让我们一步步看。

首先我们取得模式串的next数组—next_value，之后确定目标串的开始比较的位置pos（用户传入进来的参数）和模式串开始比较的位置（肯定初始化为0咯）

    next_values = get_next(format_str)

    i = pos
    j = 0

在进入while循环之前我们要知道，KMP算法进行模式匹配时，目标串的被匹配的位置即pos（循环里的i）是不会后退的而是一直往前加的，然后模式串被匹配的位置j也是动态变化的。所以while循环结束的条件是pos（循环里的i）一直加到目标串最后一个字符的位置（表示匹配失败）或者j达到模式串最后一个字符的位置（表示匹配成功）。OK，下面来看while循环中的内容：

    while i < len(des_str) and j < len(format_str):
        if j == -1 or des_str[i] == format_str[j]:
            i += 1
            j += 1
        else:
            j = next_values[j]

第一个代码块是一个if-else判断语句，if的后一部分好理解，如果目标串和模式串对应位置的值相等，则i和j都加1，然后去比较双方的下一个字符是否相等。那么前面一部分是什么意思呢？为什么j == -1也要让i和j都加1呢？看到这里有疑惑不要着急，我们先看else部分，把if的前一部分先放着，后面会讲清楚的。else语句只有当j== -1或者模式串在j位置上的字符和目标串i位置上的字符不一样才会触发，其内容是把next数组中j位置上的值赋给了j。这句话的意思就是：

当模式串在j上与目标串不匹配，则更新下次和目标串进行匹配的位置j，而更新后的值就是next数组在j上的值

理解了else，再看上面的if语句中的前一部分，即j == -1。我们知道j初始化是0的，并且对j的改变也是j += 1，所以j不可能取到-1。因此只有一种情况，就是模式串在j和目标串在i上的字符不一样，然后else语句中j的值被更新成了-1！这也说明next数组中有些位置上的值是-1，但这里我可以先告诉大家：只有next数组的第一个值是-1，也就是只有模式串的第一个位置和目标串不匹配时，才会把j更新成-1。而j变成-1后，i和j又都加1（j加1变成了0）了，这其实就是说：

当模式串的第一个字符就和目标串的对应字符不一样，则让模式串的第一个字符和目标串的下一值字符比较

最后看看while循环结束后的部分

    if j == len(format_str):
        return True, i - len(format_str)
    else:
        return False, None

上面提到过，while结束的条件只有两个，一个是i加到了目标串的结尾，也就是目标串全部匹配完了，这种情况一般就是匹配失败了（当然也不排除目标串的最后一个子串是模式串，那此时i==j），另一个是j加到了模式串的结尾，也就是模式串全部匹配完毕，说明匹配成功。

所以这里我们判断j是否等于模式串的长度，如果相等则返回True代表匹配成功，并返回i-len(format-str)表示模式串在目标串中的位置（即模式串的第一个字符在目标串中的位置）；如果不相等则返回False表示匹配失败，并返回None表示目标串中没有一个位置有模式串。

（二）求next数组

def get_next(string: str) -> list:
    length = len(string)  # 模式串长度
    next_values = [None for i in range(length)]  # 存放在当前位置不匹配时，下一次从哪个下标重新开始匹配(存储前面的字符串中最长前缀)

    next_values[0] = -1  # 如果第一个就不匹配，则索引各加一
    next_values[1] = 0

    j = 0  # 子串前缀最后一个字符
    i = 1  # 子串后缀最后一个字符

    while i < length - 1:
        if string[i] == string[j] or j == -1:
            i += 1
            j += 1
            next_values[i] = j
        else:
            j = next_values[j]

    return next_values

首先要清楚求的next数组是什么东西：我们说求next数组其实求的是模式串的next数组。其长度等于模式串的长度，即模式串中的每个字符都在next数组中有值。那么这个值到底是什么东西？这点一定要搞清楚否则连要求的是什么都搞不清楚，那么整个算法也就搞不清楚了。next数组中的每个位置上的值就是：

在这个位置上的字符S，它前面的那一个字符串（不包括字符S本身）的最大前缀或者最大后缀（因为最大前缀和最大后缀是相等的）的长度。
最大前缀（或者最大后缀）：
假设有一个字符串ababa，它的前缀有：a,ab,aba,abab,ababa；它的后缀有：a,a,ba,aba,baba，则最大前缀（或者最大后缀）就是aba,因为它同时属于字符串的前后缀，并且长度在同属前后缀的子串中最长！
例：ababad，它的next数组就是[-1, 0, 0, 1, 2, 3]。这里解释一下，next数组的前两个值固定为-1和0，-1是方便处理模式串第一个字符就不匹配的情况，而0是因为在第二个字符前只有一个字符a，而单个字符a是没有前缀的。它和后面的第三个a不一样，这个是因为它前面的字符串ab没有最大前缀（或者最大后缀），所以设为0；第二个a是可以确定根本就没有前缀，直接敲定为0。

想必看到这里大家应该都知道这个next数组是个什么东西了吧😜，接下来就正式讲解如何求解next数组。

首先我们根据传进来的模式串的长度创建一个列表作为next数组，并把next数组前两位直接设置为-1和0，原因上面解释过了。

    length = len(string)  # 模式串长度
    next_values = [None for i in range(length)]  # 存放在当前位置不匹配时，下一次从哪个下标重新开始匹配(存储前面的字符串中最长前缀)

    next_values[0] = -1
    next_values[1] = 0

然后我们再从具体例子中实验区发现一些有趣的规律，这里拿ababad结合下面的代码举例：

首先while循环的条件是i < length - 1，减一的操作是防止列表越界，比如长度为8，i==7通过了i < length==8的判断，然后从7加到8了但是列表next_value[i == 8] = j就越界了。

第一个我们求next[2]。按照求最大前缀长度的方法，这里就是用第三个字符a前面的字符串ab中的第一个字符a和第二个字符b比较，我们可以设立j = 0，i= 1，分别代表字符串的第一个字符和最后一个字符的位置。然后看看模式串在ij位置的字符是否一样，如果一样则next[2]就为1，如果不一样则next[2]就为0。

这里a不等于b，我们知道next[2] =0。但是代码该怎么写呢？我们发现，在之前已经可以肯定next数组前两个数就会是-1和0，所以我们就让j = next_value[j]，即让j更新。这里j更新后的值是-1，然后重新判断得到结果是ij都加1，即i = 2, j = 0，此时我们可以得到next_value[i==2] = (j==0)。看到这里有没有发现，此时的j的值正好就是此时next数组在i上的值。有点意思，我们继续往下看：

第二个我们求next[3]。此时i=2,j=0,然后我们发现aba的最大前缀是a，长度为1，那么next[3]应该为1.再看代码部分，恰好有string[i==2] == string[j==0] == a，然后ij都加1，next_value[i==3] == (j==1)，是不是也满足此时的j的值正好就是此时next数组在i上的值。

第三个我们求next[4]。此时i=3，j=1,然后我们发现abab的最大前缀是ab，长度为2，那么next[4]应该为2.再看代码部分，恰好有string[i==3] == string[j==1] == b，然后ij都加1，next_value[i==4] == (j==2)，也满足此时的j的值正好就是此时next数组在i上的值。

于是我们不难发现写代码的规律：即从j=0,i=1开始，比较模式串在ij上的值，如果一样或者j==-1则ij都加1然后next[i] = j。如果不一样，则从next中取值更新j,方法就是j=next[j]

    j = 0  # 最长的前缀子串最后一个字符
    i = 1  # 最长的后缀子串最后一个字符     
  
    while i < length - 1:
        if string[i] == string[j] or j == -1:
            i += 1
            j += 1
            next_values[i] = j
        else:
            j = next_values[j]

    return next_values

讲实话相信原理大家都懂，让大家手写next数组应该也都会，就是代码理解和实现有困难。我个人觉得代码理解和原理理解不一样，具体去写代码还是要多写才可以发现一些规律，才能把我们人脑理解的东西用代码表示出来。