kmp模式匹配算法求next代码讲解

KMP算法是一种字符串匹配算法，其中的next数组是KMP算法中非常重要的一个概念。next数组记录了模式串中前缀和后缀相同的最大长度。

举个例子，如果模式串为"ABCDABD"，那么它的next数组为[0,0,0,0,1,2,0]。其中，next = 0，next = 0，next = 0，next = 0，next = 1，next = 2，next = 0。

下面是KMP算法求next数组的代码讲解：

def get_next(p: str) -> List[int]:
    n = len(p)
    # 初始化next数组
    next =  * n
    # i为后缀末尾位置，j为前缀末尾位置
    i, j = 1, 0
    while i < n:
        if p[i] == p[j]:
            # 如果当前字符匹配成功，则将next[i]设置为j+1
            next[i] = j + 1
            # i和j同时向后移动一位
            i += 1
            j += 1
        elif j > 0:
            # 如果字符不匹配，并且j>0，则将j更新为next[j-1]
            j = next[j-1]
        else:
            # 如果字符不匹配，并且j=0，则将next[i]设置为0，i向后移动一位
            next[i] = 0
            i += 1
    return next

该函数接受一个字符串p作为参数，返回一个整型数组。其中，数组中第i个元素表示模式串p中以i结尾的子串的最长前缀和后缀相同的长度。