KMP算法：如何通过 next 数组推导模式串该从哪里继续匹配
目录
一、next 数组的本质：模式串的 “记忆地图”
二、计算 next[j] 的核心逻辑（递推法）
情况 1：t[j] == t[k]（k = next[j]）
①j + 1 是啥？
② next[j + 1] = next[j] + 1 是啥意思？
③ 结合例子，一步一步看（下标从 1 开始）
1. 初始值：next[1] = 0
2. 计算 next[2]（j = 1，算 j + 1 = 2）
3. 计算 next[3]（j = 2，算 j + 1 = 3）
4. 计算 next[4]（j = 3，算 j + 1 = 4）
5. 计算 next[5]（j = 4，算 j + 1 = 5）
④ 总结规律
情况 2：t[j] != t[k]（k = next[j]）
四、next 数组如何指导 “从哪继续匹配”？
五、总结：next 数组的 “找位置” 逻辑
这里的数组下标从1开始
一、next 数组的本质：模式串的 “记忆地图”
想象模式串是一条路，每个位置 j 是一个 “岔路口”。当在 j 位置匹配失败时，next[j] 会告诉你：“别慌，回到前面这个位置 k，从这里重新走，能复用之前的匹配成果！”
这个 k 是模式串中 j 之前的子串的 “最长相等前缀和后缀的长度”（专业说法是 “最长公共前后缀”）。
二、计算 next[j] 的核心逻辑（递推法）
已知 next[0...j]，求 next[j+1]，分两种情况：
情况 1：t[j] == t[k]（k = next[j]）
- 类比：你在模式串的
j位置，发现当前字符和k位置字符一样，说明 “前缀能续上”。 - 结论：
next[j+1] = next[j] + 1（最长公共前后缀长度 +1）。
①j + 1 是啥？
j 是模式串当前处理到的位置（下标从 1 开始），j + 1 就是下一个要计算 next 值的位置。
比如：
- 当你算完
next[1], next[2], ..., next[j]，下一步要算next[j + 1]，看模式串第j + 1个字符失配时该回退到哪。
② next[j + 1] = next[j] + 1 是啥意思？
这是 next 数组递推的核心规律：
如果 模式串第 j 个字符 和 模式串第 next[j] 个字符 相等，那么 next[j + 1] 就等于 next[j] + 1。
换句话说：
因为 “
j位置的字符” 能和 “next[j]位置的字符” 匹配，所以 “j + 1位置” 的最长公共前后缀长度，就是 “j位置的最长公共前后缀长度 + 1”。
③ 结合例子，一步一步看（下标从 1 开始）
假设模式串 T = "ababc"（字符下标 1~5 对应 a,b,a,b,c），手动推导 next 数组：
1. 初始值：next[1] = 0
模式串第一个字符（T[1] = 'a'），没有前缀，所以 next[1] = 0（特殊规则）。
2. 计算 next[2]（j = 1，算 j + 1 = 2）
j = 1，next[j] = next[1] = 0。- 比较
T[j]（T[1] = 'a'）和T[next[j]]（T[0]不存在，所以next[2] = 1（另一种特殊规则：若next[j] = 0，则next[j + 1] = 1）。
3. 计算 next[3]（j = 2，算 j + 1 = 3）
j = 2，next[j] = next[2] = 1。- 比较
T[j]（T[2] = 'b'）和T[next[j]]（T[1] = 'a'）→'b' != 'a'，所以不能直接用next[j] + 1。 - 此时需要回溯
next[j]到next[1] = 0，再比较T[2]和T[0]（不存在），最终next[3] = 1。
4. 计算 next[4]（j = 3，算 j + 1 = 4）
j = 3，next[j] = next[3] = 1。- 比较
T[j]（T[3] = 'a'）和T[next[j]]（T[1] = 'a'）→'a' == 'a'。 - 所以
next[j + 1] = next[j] + 1 → next[4] = 1 + 1 = 2。
5. 计算 next[5]（j = 4，算 j + 1 = 5）
j = 4，next[j] = next[4] = 2。- 比较
T[j]（T[4] = 'b'）和T[next[j]]（T[2] = 'b'）→'b' == 'b'。 - 所以
next[j + 1] = next[j] + 1 → next[5] = 2 + 1 = 3。
④ 总结规律
j + 1是下一个要计算next值的位置，代表模式串的 “当前处理位置 + 1”。next[j + 1] = next[j] + 1的条件是：模式串第j个字符 ≡ 模式串第next[j]个字符。- 这一步的本质是：利用模式串自身的 “部分匹配”，让
next数组 “继承” 匹配长度，避免重复计算。
简单说，j + 1 是递推的 “下一步位置”，next[j] + 1 是 “能复用匹配成果时的递推公式”—— 核心就是用已知的 next[j] 推导未知的 next[j + 1] ，让模式串自己 “记住” 该回退到哪。
情况 2：t[j] != t[k]（k = next[j]）
- 类比：当前字符不匹配，说明 “这条路走不通，得回到
k的‘记忆位置’重新找”。 - 结论：让
k = next[k]，重复比较，直到k=0或找到相等字符。
示例（模式串 t = "ababca"）：
- 假设
j=5（字符a），k = next[5] = 2（已算出）。 - 若
t[5] != t[2]（a != b），则k = next[2] = 0，再比较t[5]与t[0]（若相等则next[6] = 0 + 1 = 1）。
四、next 数组如何指导 “从哪继续匹配”？
当模式串在 j 位置失配时：
- 直接让
j = next[j]，跳到模式串的next[j]位置，继续和主串当前i位置比较。
五、总结：next 数组的 “找位置” 逻辑
- 计算
next[j]：通过递推，利用 “最长公共前后缀” 找模式串自身的回溯位置。 - 使用
next[j]：失配时，模式串指针j跳到next[j]，主串指针i不回退，直接继续比较。