时间：2022/10/12
一. next数组原理的说明
KMP算法一般用于解决字符串匹配的问题，在KMP算法出现之前，字符串匹配一般通过双层for循环的暴力方法解决，时间复杂度为O(n*m)，其中n为主串的长度，m为子串的长度。而KMP算法的出现使字符串匹配的时间复杂度减少到O(n+m)，他的主要思想是由于已经知道之前遍历过的字符，那是否可以利用这些信息来避免暴力算法中主串指针回退的步骤，这样主串指针就可以永远向前移动，从而达到线性时间的时间复杂度。具体可以参照下图：
从上面我们也可以看出，KMP算法的核心在于next数组的构建。那next数组的本质是什么呢？其实就是一个前缀表，用来记录下标i之前（包括i）的字符串中，有多大长度相同前缀和后缀。它的作用是用来在主串字符和子串字符不相等时来回退，它记录了主串和子串不匹配的时候，子串应该从哪里开始重新匹配。可以通过下图来理解next数组的作用：
在解释了next数组的含义与next数组的作用之后，接下来最重要的就是如何构建next数组。求解子串next数组主要分为两步：首先是初始化，这里我们要初始化三个值，第一个值是next[0]=0，即对于第一个字符的最长相等前后缀的长度为0，这是很好的理解的，网上对于next[0]的初始化值有不同的方案，个人感觉这里初始化为0比较好理解，第二值是prefix_len=0，该值表示的是i之前的字符组成的字符串的最长相等前后缀长度，即当前最长相等前后缀的长度，也可以理解为要比较的下标值（这里为什么说prefix_len可以作为要比较的下标值，可以假设prefix_len=2，说明对于i之前的字符来说，前两个字符组成的前缀和后两个字符组成的后缀是相等的，所以此时要跳过前两个字符来从第三个字符开始比较，又由于数组的下标从0开始，所以第三个数组的下标为2，也就是prefix_len的值），一开始的时候为0，第三个值是子串指针i，也就是for循环的循环变量，这里初始化为1，因为next[0]已经初始化为0，接下来要求的是next[1]；初始化完成之后就要开始求next[i]的值，这时会有两种情况，分别是前后缀相等的情况和前后缀不相等的情况，这里的前后缀是否相等比较的是prefix_len处的字符是否与i处的字符相等，因为前面也说了prefix_len可以理解为要比较的下标值，相等的时候比较容易理解，此时next[i]=prefix_len+1，这是因为对于前面i-1个字符来说，它们的前prefix_len个字符与后prefix_len个字符相等，若下标为prefix_len处的字符（也就是第prefix_len+1个字符）与下标为i的字符相等，那么对于前i个字符来说，前prefix_len+1个字符与后prefix_len+1个字符也相等，即next[i]=prefix_len+1。相比于前后缀相等的情况，前后缀不相等的情况会更难理解一些，若prefix_len处的字符与i处的字符不相等，那么需要令prefix_len=next[prefix_len]，此时再比较两处的字符是否相等，若不相等则一直循环，以下面的字符串ababaf为例，求next[5]的值，也就是指针i指向了字符f，此时的prefix_len=2，即对于字符串ababa来说，前两个字符ab等于后两个字符ab，由于prefix_len=2，此时需要比较下标为2的字符a是否与下标为5的字符f相当，很明显不相等，此时令prefix_len=next[prefix_len]=next[2]=1，然后再比较下标为1处的字符b是否与下标为5处的字符f相等，可能大家在这里对于操作prefix_len=next[prefix_len]不理解，其实可以这样理解，在之前prefix_len=2时，说明对于字符串ababa来说，前两个字符ab与后两个字符
标签：字符,相等,后缀,prefix,len,next,算法,KMP From： https://www.cnblogs.com/machi12/p/16783850.html