关于KMP算法失效函数两种定义及递归计算逻辑的疑问

我正在通过《Fundamentals of Data Structures in C》学习Knuth-Morris-Pratt (KMP)算法，书中给出了失效函数f(j)的两种定义：

• 若模式p="p₀p₁…pₙ₋₁"，f(j)定义为：存在i≥0时，f(j)是满足p₀p₁…pᵢ = pⱼ₋ᵢpⱼ₋ᵢ₊₁…pⱼ的最大i<j；否则f(j)=-1。
• 重述定义：j=0时f(j)=-1；存在最小整数k使得p[fₖ(j-1)+1]=p[j]时，f(j)=fₘ(j-1)+1（其中f₁(j)=f(j)，fₘ(j)=f(fₘ₋₁(j))）；无满足条件的k时f(j)=-1。

疑问1：失效函数返回值差异的原因 #

网络资料中失效函数返回模式局部最长真后缀同时也是前缀的长度，而书中定义返回最长真前缀同时也是后缀的结束索引，这个差异确实由0-based和1-based索引环境导致：

• 采用1-based索引时，最长匹配前缀的长度等于其结束索引（例如前缀p₁p₂p₃长度为3，结束索引也是3），因此返回长度与返回结束索引等价。
• 书中基于C语言的0-based索引，最长匹配前缀的结束索引i对应的长度为i+1（例如前缀p₀p₁结束索引为1，长度为2）。网络资料中的“长度”表述，本质是将0-based的结束索引加1后的结果，二者逻辑完全一致，只是表述和索引习惯不同。

疑问2：递归计算失效函数的可行性与无遗漏性 #

重述定义中通过前一位置的失效函数递归计算当前值的方式可行且不会遗漏潜在匹配，核心在于失效函数的“最长匹配”特性具备传递性：

1. 计算f(j)时，首先检查f(j-1)对应的最长匹配前缀的下一个字符（即p[f(j-1)+1]）是否等于p[j]：若相等，最长匹配可直接延长，f(j)=f(j-1)+1，这是最优情况。
2. 若不相等，说明f(j-1)对应的最长匹配无法延长，此时需要寻找次长的有效匹配——而次长匹配恰好是f(f(j-1))对应的前缀（因为f(f(j-1))是f(j-1)位置的最长匹配，即原最长匹配前缀中的最长匹配后缀）。
3. 以此递归遍历，直到找到某个fₖ(j-1)使得p[fₖ(j-1)+1] = p[j]，此时对应的匹配即为当前最长有效匹配；若递归至fₖ(j-1)=-1仍不匹配，则说明无有效匹配，f(j)=-1。

以模式"ababyababa"的f(9)为例：

• 先获取f(8)的值m，检查p[m+1]与p[9]是否相等：
  • 若相等，直接得到f(9)=m+1；
  • 若不相等，则递归获取f(m)，再检查p[f(m)+1]与p[9]，依此类推。
    这个过程不会遗漏潜在匹配，因为失效函数的递归链覆盖了所有“真前缀=真后缀”的长度递减序列——每一步递归都在寻找更短的符合条件的匹配，直到找到第一个能与当前字符匹配的位置，或确认无匹配。

内容的提问来源于stack exchange，提问作者鄒鄒寶寶