数据结构kmp算法 next数组

KMP算法是一种字符串匹配算法，用于在一个主串S内查找一个模式串P的出现位置。其中next数组是KMP算法的核心部分，它存储了每个前缀和后缀的最长公共部分长度。

具体来说，假设在主串S中找到了一个与模式串P的前k个字符相同的子串，但是第k+1个字符不匹配，那么我们可以利用next数组，将模式串P向右移动j-next[j]个位置，继续与主串S中的第k+1个字符进行匹配，其中j为当前已匹配的字符数。

下面是next数组的求解过程：
1. 初始化next = -1，next = 0；
2. k表示当前已匹配的字符数，j表示当前正在匹配的字符数；
3. 如果P[k] == P[j]，那么next[j+1] = k+1，并且将k和j都加1；
4. 否则，令k = next[k]，如果k == -1，则令next[j+1] = 0，并且将j加1；
5. 重复步骤3和步骤4，直到j等于模式串P的长度。

相关问题

kmp算法next数组的算法编程

KMP算法，全称为Knuth-Morris-Pratt算法，是一种用于字符串匹配的高效算法，尤其适合处理文本搜索中的坏字符规则。其中的核心数据结构是next数组，也称作部分匹配表。

next数组的作用是存储模式串中每个位置之前失败的位置对应的索引。当模式串的一个字符与目标串的某个字符不匹配时，而不是从头开始查找，而是从上次失败的位置之后继续比较。构建next数组的过程如下：

1. 初始化：`next[0] = -1`，表示空模式或前缀都是匹配成功的。
2. 遍历模式串（从第二个字符开始）：
a. 如果当前字符与前一个字符相等，则`next[i] = next[i-1] + 1`，说明匹配成功，将指向前一个已匹配的下一个字符。
b. 否则，检查从`next[next[i]]`到`i-1`之间的所有字符是否都与`i`相同。如果找到相同的，设置`next[i] = j`，表示模式串中从`j+1`开始的部分可以与当前位置之前的子串匹配；如果没有找到，将`next[i]`设为`-1`，并移动到模式串的第一个字符重新开始尝试。

通过这种方式，KMP算法避免了无效的回溯，提高了搜索效率。构建好next数组后，在实际匹配过程中，如果目标串中有字符与模式串不匹配，可以直接依据next数组跳过相应位置继续匹配。

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开始。