kmp算法next计算方法

KMP Next数组计算方法：初始化Next[0] = -1，Next[1] = 0。遍历模式串从第二个字符开始。如果当前字符与Next[i-1]指向的字符相等，则Next[i] = Next[i-1] + 1。如果当前字符与Next[i-1]指向的字符不相等且Next[i-1]不为0，则i = Next[i-1]，重复步骤3。如果当前字符与Next[i-1]指向的字符不相等且Next[i-1]为0，则Next[i] = 0。重复步骤

KMP Next数组计算方法

问题：如何计算KMP算法中的Next数组？

回答：

KMP算法的Next数组用于记录模式串中每个字符之前最长的前缀和后缀匹配长度。Next数组的计算方法如下：

步骤：

1. 初始化：Next[0] = -1，Next[1] = 0。
2. 开始遍历模式串从第二个字符开始：

3. 如果当前字符与Next[i-1]指向的字符相等：

   

   js随机数学加法计算答题代码

   一款js随机数学加法计算答题代码

   16

   查看详情
   • Next[i] = Next[i-1] + 1

4. 如果当前字符与Next[i-1]指向的字符不相等且Next[i-1]不为0：

   • i = Next[i-1]，重复步骤2

5. 如果当前字符与Next[i-1]指向的字符不相等且Next[i-1]为0：

   • Next[i] = 0
6. 重复步骤2~5，直到遍历完模式串。

示例：

计算模式串“ababaca”的Next数组：

<code>i    | 1    | 2    | 3    | 4    | 5    | 6    | 7
Next[i]    | -1    | 0    | 0    | 1    | 0    | 1    | 2</code>

注意：

• Next[0]始终为-1，这是为了方便算法的实现。
• Next[1]始终为0，因为长度为1的字符串的前缀和后缀匹配长度为0。
• 当当前字符与Next[i-1]指向的字符不相等且Next[i-1]不为0时，需要回溯到Next[i-1]，继续寻找最长的前缀和后缀匹配。

以上就是kmp算法next计算方法的详细内容，更多请关注php中文网其它相关文章！