KMP算法：匹配与LPS表计算阶段的回退逻辑类比及原理疑问

一、匹配阶段与LPS计算阶段回退的类比关系 #

两者本质是同一逻辑的两种应用场景，核心都是「利用已匹配的前缀信息，跳过无意义的重复比较」：

• 匹配阶段：你拿着模式串匹配外部文本，当某位置字符不匹配时，文本指针不动，模式指针回退到lps[j-1]的位置——这是因为你已经确认模式串的前j个字符和文本对应前缀完全匹配，而lps[j-1]是这个前缀的最长相等前后缀长度，回退到这里就能直接复用之前的匹配结果，不用从头开始比对。
• LPS计算阶段：你拿着模式串的前缀匹配自身的前缀，计算lps[i]时，如果pattern[i]和pattern[len]（len是当前找到的最长相等前后缀长度）不匹配，就把len回退到lps[len-1]——这和匹配阶段的回退逻辑完全一致：你已经知道模式串的前len个字符和pattern[0..i-1]的某个前缀匹配，回退到lps[len-1]就是复用这个匹配结果，继续找更长的相等前后缀。

简单说，两者都是基于已有的匹配历史，用最长相等前后缀减少重复比较，区别只是一个是模式对外部文本，一个是模式前缀对自身前缀。

二、LPS计算阶段的“文本”与“模式”是什么 #

LPS计算的本质是模式串自己和自己做匹配：

• 这里的「文本」是模式串的前缀子串pattern[0..i]（i从0到模式串长度-1），我们要在这个子串里找最长的相等前后缀。
• 这里的「模式」是模式串本身的前缀，我们用它去匹配上面的“文本”前缀。

举个具体例子：计算pattern = "ABABC"的lps数组时，当i=3（对应字符'A'），我们用pattern[0..len]（此时len=1，对应子串"AB"）去匹配pattern[0..3]（子串"ABAB"），发现pattern[3]（'A'）和pattern[len]（'B'）不匹配，于是把len回退到lps[len-1] = lps[0] = 0，此时pattern[3]和pattern[0]匹配，len更新为1，所以lps[3] = 1。整个过程和用模式串匹配外部文本的逻辑完全一致，只是“文本”和“模式”都是模式串自己的一部分。

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