KMP 算法模式匹配：next 数组详解

KMP 算法是一种高效的字符串匹配算法。在 KMP 算法中，next 数组用于记录模式串中前缀与后缀的最长公共前缀长度，从而在匹配过程中避免不必要的回溯。

对于模式串 'abadaabcd'，其 next 数组的值为 [8, 2, 1, 2, 1, 2, 2, 3, 1]。

next 数组的计算方法：

1. 初始化：next[0] = 0。
2. 遍历模式串：从 i = 1 开始，逐步计算 next[i]。
3. 设置 j = next[i - 1]。
4. 比较当前字符和第 j 个字符：
   • 如果模式串的第 i 个字符和第 j 个字符相同，则 next[i] = j + 1。
   • 否则，将 j 赋值为 next[j]，并重复步骤 4。
5. 如果 j 等于 0，则 next[i] = 0。

以 'abadaabcd' 为例说明 next 数组的计算过程：

| i | 字符 | j | next[i] | 说明 | |---|---|---|---|---| | 0 | 'a' | - | 0 | 初始化 | | 1 | 'b' | 0 | 0 | 'b' 和 'a' 不相同，j = next[0] = 0 | | 2 | 'a' | 0 | 1 | 'a' 和 'a' 相同，next[2] = j + 1 = 1 | | 3 | 'd' | 1 | 0 | 'd' 和 'b' 不相同，j = next[1] = 0 | | 4 | 'a' | 0 | 1 | 'a' 和 'a' 相同，next[4] = j + 1 = 1 | | 5 | 'a' | 1 | 2 | 'a' 和 'b' 不相同，j = next[1] = 0，'a' 和 'a' 相同，next[5] = j + 1 = 2 | | 6 | 'b' | 2 | 1 | 'b' 和 'd' 不相同，j = next[2] = 1，'b' 和 'a' 不相同，j = next[1] = 0，'b' 和 'a' 不相同，j = next[0] = 0 | | 7 | 'c' | 0 | 2 | 'c' 和 'a' 不相同，j = next[0] = 0，'c' 和 'b' 不相同，j = next[1] = 0，'c' 和 'a' 相同，next[7] = j + 1 = 2 | | 8 | 'd' | 2 | 3 | 'd' 和 'a' 不相同，j = next[2] = 1，'d' 和 'b' 不相同，j = next[1] = 0，'d' 和 'a' 相同，next[8] = j + 1 = 3 | | 9 | 'a' | 3 | 1 | 'a' 和 'c' 不相同，j = next[3] = 0，'a' 和 'a' 相同，next[9] = j + 1 = 1 |

因此，对于模式串 'abadaabcd'，next 数组的值为 [8, 2, 1, 2, 1, 2, 2, 3, 1]。