KMP算法LPS表的核心思想是什么

Question

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

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

Answer 1

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

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

以

s="AABAACAABAAB"

为例，当尝试将最后一个字符“B”与s[5]（即字符“C”）匹配时，我们实际上是在尝试将文本“AABAAB”与模式“AABAAC”匹配，现在发生不匹配，然后，我们返回到 s[LPS[5-1]]，而不是返回到第一个字符，即 2。