KMP算法中为何用length=prefixTable[length-1]而非length=length-1？

核心差异：暴力回退 vs 智能回溯 #

前缀表的每个元素prefixTable[i]，表示字符串s[0..i]的最长相等前后缀的长度。当s[i] != s[length]时，我们需要回退length寻找更短的匹配前后缀：

• 直接length--是暴力回退，每次仅缩短1位，相当于逐个尝试更短的前后缀，时间复杂度会退化为O(n²)。
• length = prefixTable[length - 1]是利用已计算的前缀表信息，直接跳转到当前最长可能匹配的前后缀长度，避免无效尝试，保证整个前缀表构建过程是O(n)的线性时间。

示例对比：复杂字符串下的效率差异 #

以字符串s = "ABABABAC"为例，对比两种写法处理i=7（字符'C'）时的区别：

正确写法（length = prefixTable[length - 1]） #

1. 处理到i=7时，length的值为5（i=6时prefixTable[6]=5，对应s[0..6]的最长相等前后缀长度为5）。
2. 由于s[7] = 'C' != s[5] = 'B'，执行length = prefixTable[5-1] = prefixTable[4] = 3——直接跳转到长度3，这是s[0..4]的最长相等前后缀长度，直接定位到最可能的匹配位置。
3. 此时s[7] != s[3] = 'B'，继续执行length = prefixTable[3-1] = prefixTable[2] = 1。
4. 仍不匹配，执行length = prefixTable[1-1] = prefixTable[0] = 0，循环结束。
   整个回退过程仅3次跳转。

暴力写法（length--） #

1. 初始length=5，s[7] != s[5]，执行length=4。
2. s[7] != s[4] = 'A'，执行length=3。
3. s[7] != s[3] = 'B'，执行length=2。
4. s[7] != s[2] = 'A'，执行length=1。
5. s[7] != s[1] = 'B'，执行length=0，循环结束。
   整个回退过程需要5次操作，比正确写法多了2次无效比较。

如果字符串更长、重复模式更复杂，这种无效操作的差距会被放大，最终导致暴力回退的写法时间效率急剧下降。

总结 #

length = prefixTable[length - 1]是KMP算法高效的核心之一，它通过复用前缀表的已有计算结果，跳过所有不可能匹配的短前后缀，直接定位到最优匹配位置，保证了算法的线性时间复杂度。而直接length--是暴力回溯思路，虽在简单字符串下结果一致，但复杂场景下会产生大量无效操作，时间效率远低于正确写法。

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