使用LPS表时不匹配后的回退与计算LPS表本身时有何类比？

Question

我比较了解KMP算法的主要部分，就是根据LPS表出现不匹配时回退。

但是，我总是对计算/创建 LPS 表本身时的回退感到困惑，也就是说，在这种情况下，文本和模式分别是什么？谁能与我分享一些其背后的核心直觉，以帮助我更好地理解它？

Answer 1

经过一番苦苦思索，我想我终于灵光一现了。

打个比方，在计算 LPS 表时，我们实际上是在尝试将文本（最后 n+1 个字符，即后缀）与模式（前 n+1 个字符，即前缀）进行匹配，其中 n 是长度已经匹配，这个类比的 LPS 表是到目前为止创建的部分 LPS。

以

s="AABAACAABAAB"

为例，当尝试将最后一个字符“B”与s[5]匹配时，我们实际上是在尝试将文本“AABAAB”与模式“AABAAC”进行匹配，现在发生了不匹配，然后，而不是返回回到第一个字符，我们返回到

s[LPS[5-1]]

，即 2。