kmp算法next计算方法_【数据结构——串】KMP算法——next数组Python的实现方式

KMP算法中的next数组是用来记录模式串中前缀和后缀的最长公共部分的长度的数组。计算next数组的方法如下：

1. 初始化：next[0] = -1，i = 0，j = -1。

2. 进入循环，判断 i 是否小于模式串的长度，若小于则执行循环体，否则退出循环。

3. 在循环体中，首先判断 j 是否等于-1或者当前字符等于模式串中的字符 j，若满足条件则 i 和 j 同时加1。

4. 若不满足条件，则将 j 更新为 next[j]，直到满足条件。

5. 更新 next[i] 为 j。

6. 返回 next 数组。

下面是Python实现代码：

def get_next(pattern):
    n = len(pattern)
    next_arr = [-1] * n
    i, j = 0, -1
    while i < n - 1:
        if j == -1 or pattern[i] == pattern[j]:
            i += 1
            j += 1
            next_arr[i] = j
        else:
            j = next_arr[j]
    return next_arr

注意，该算法中的模式串下标从0开始。

相关问题

kmp算法next数组python

KMP算法的next数组在字符串匹配中非常重要，它可以帮助我们快速移动模式串的指针，提高匹配效率。

下面是KMP算法next数组的Python实现：

def get_next(p):
    """
    计算next数组
    """
    n = len(p)
    next = [0] * n
    j = 0
    for i in range(1, n):
        while j > 0 and p[i] != p[j]:
            j = next[j-1]
        if p[i] == p[j]:
            j += 1
        next[i] = j
    return next

其中，p表示模式串，next数组的长度与模式串的长度相同，next[i]表示模式串中前i个字符的最长公共前后缀的长度。

该函数的实现过程为：从第二个字符开始遍历模式串，利用while循环找到当前字符的最长公共前后缀的长度，然后将该长度赋值给next数组中对应的位置。

注意，当p[i]不等于p[j]时，需要利用next[j-1]来更新j的值，因为next[j-1]表示的是p[0:j]的最长公共前后缀的长度，而p[0:j]与p[1:i]的最长公共前后缀的长度是相同的。

用python写一段代码实现用KMP算法中的求字串next数组的算法求出串aabaaabaac的next数组。

好的，针对您的问题，以下是Python的KMP算法求字串next数组的代码实现：

def get_next(sub_str):
    n = len(sub_str)
    next_arr = [0] * n
    i, j = 1, 0
    while i < n:
        if sub_str[i] == sub_str[j]:
            j += 1
            next_arr[i] = j
            i += 1
        elif j > 0:
            j = next_arr[j - 1]
        else:
            next_arr[i] = 0
            i += 1
    return next_arr

# 调用方法
sub_str = "aabaaabaac"
next_array = get_next(sub_str)
print(next_array)

运行结果为 [0, 1, 0, 1, 2, 3, 0, 1, 1, 0] 。