KMP算法失配回退时为何取预构建数组值而非从头开始？正确性如何保证

问题1：失配时为什么从预构建数组取值跳转，而非从头匹配？如何保证跳转后匹配结果正确？ #

KMP算法设计的核心目标是避免暴力匹配中无意义的重复比较，预构建的arr数组（业内通常叫前缀函数/next数组）就是为了存储已匹配片段的公共前后缀信息。

• 不从头匹配的原因：当模式串和主串匹配到第i位失配时，前i位已经完成了匹配验证，这段已匹配的子串一定存在相等的真前缀和真后缀（最短是长度0）。如果直接从头匹配，等于把已经确认相等的前后缀部分再重新比一遍，完全是冗余操作。
• 正确性保证：前缀函数arr[k]的定义是「模式串前k+1个字符组成的子串中，最长相等真前缀和真后缀的长度」。失配时跳转的长度就是已匹配子串的最长相等前后缀长度，跳转后前缀的这部分字符和主串对应位置的后缀字符已经经过之前的匹配验证，100%相等，不需要重复比较，所以不会出错。

举个简单例子：模式串为aabaa，匹配到第5位（下标4）时失配，已匹配的前4位是aaba，它的最长相等前后缀是长度1的a，所以直接跳到下标1的位置继续匹配即可，不需要回到下标0重新比第一个a，因为我们已经确定主串对应位置是a，和模式串第一个字符相等。

问题2：i > 0 and charAt(i) != charAt(j) then i = arr[i-1]的具体工作原理 #

这行代码是**构建前缀函数数组arr**时的核心回退逻辑，先明确两个变量的定义：

• j：遍历模式串的指针，从下标1开始遍历（单字符没有真前后缀，所以arr[0]固定为0）
• i：当前尝试和s[j]匹配的前缀末尾指针，初始值为0

逻辑说明 #

当同时满足两个条件：i不等于0（已经匹配了至少一个前缀字符）、当前i位置的字符和j位置的字符不相等时，我们不需要把i直接回退到0，而是回退到arr[i-1]的位置，用更短的相等前缀继续尝试和s[j]匹配，直到i为0或者字符相等为止。
这个回退逻辑本质和匹配阶段的失配跳转是完全一致的：利用已经算好的更短子串的前缀函数结果，避免重复比较。

结合你给出的示例验证 #

你的模式串和初始参数如下：

下标 0 1 2 3 4 5 6 7 8
s =  a a b a a b a a a
arr初始：[0, ?, ?, ?, ?, ?, ?, ?, ?]
i=0，j从1开始遍历

我们走前几步的计算流程就能清晰看到逻辑：

1. j=1，s[i]=s[0]='a'，s[j]=s[1]='a'，字符相等，所以i自增为1，arr[1] = 1，j自增为2
2. j=2，s[i]=s[1]='a'，s[j]=s[2]='b'，字符不相等，且i>0，执行i = arr[i-1] = arr[0] = 0
3. 现在i=0，再次比较s[0]='a'和s[2]='b'，仍然不相等，所以arr[2] = 0，j自增为3
4. j=3，s[i]=s[0]='a'，s[j]=s[3]='a'，字符相等，i自增为1，arr[3] =1，j自增为4
5. 后续步骤重复上述逻辑，最终计算得到的arr数组就是你给出的[0, 1, 0, 1, 2, 3, 4, 5, 2]，完全匹配。

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