第一次匹配失败时：

• $i$ 停留在 $S$ 中不匹配的位置：$i = 5$

• $j$ 停留在 $T$ 中不匹配的位置：$j = 5$

3. 下一次匹配时的 $i$ 和 $j$

当匹配失败时（在 $j=5$ 处失败），KMP 算法利用 $LPS$ 数组来确定 $T$ 模式字符串应该从哪个位置开始新的匹配，而主串指针 $i$ 不回溯。

1. 计算 j 的新值：

   新的 j 值由失败位置的前一个位置 j−1 的 LPS 值决定。

   $$\text{新的 } j = LPS[j-1]$$

   • 失败时的 $j = 5$

   • $j-1 = 4$

   • $LPS[4] = 2$

   • 新的 $j = 2$

   这意味着在 $T[0 \dots 4] = \text{"abaab"}$ 中，最长公共前后缀是 $\text{"ab"}$，长度为 2。我们已经知道 $S[i-j \dots i-1]$ 与 $\text{"abaab"}$ 匹配，所以现在我们知道 $S[i-2 \dots i-1]$ 已经和 $T[0 \dots 1]$ 匹配。因此，我们从 $T[2]$ ($\text{'a'}$) 处开始尝试匹配 $S[5]$ ($\text{'a'}$)。

2. 确定 i 的值：

   在 KMP 算法中，主串指针 i 在匹配失败时保持不变，继续指向 S 中发生不匹配的位置。

   • 新的 $i = 5$

下一次匹配时：

• $i = 5$

• $j = 2$

对于字符串 "aaab"，让我逐步计算其LPS数组：

LPS数组的定义：LPS[i] 表示子串 s[0...i] 的最长相等前后缀的长度（前缀和后缀不能是整个字符串本身）。

计算过程：

• i=0 ('a')：子串 "a"
  • 没有真前后缀
  • LPS[0] = 0
• i=1 ('a')：子串 "aa"
  • 前缀："a"，后缀："a" ✓
  • LPS[1] = 1
• i=2 ('a')：子串 "aaa"
  • 前缀："aa"，后缀："aa" ✓
  • LPS[2] = 2
• i=3 ('b')：子串 "aaab"
  • 前缀："a", "aa", "aaa"
  • 后缀："b", "ab", "aab"
  • 没有匹配
  • LPS[3] = 0

答案：

字符串: a  a  a  b
索引:   0  1  2  3
LPS:    0  1  2  0

所以 "aaab" 的LPS数组是 [0, 1, 2, 0]

ababaaababaa
0 a 0
1 ab 0 
2 aba 1
3 abab 2
4 ababa 3
5 ababaa 1
6 ababaaa 1
7 ababaaab 2
8 ababaaaba 3
9 ababaaabab 4
10 ababaaababa 5
11 ababaaababaa 1

LPS 的优化数组”通常指的是 KMP 算法中的 $next$ 数组的 改进/优化版本，也常被称为 $nextval$ 数组（或 $next'$ 数组）。

1. 为什么需要优化？（LPS 数组的缺陷）

标准的 LPS 数组（或 $next$ 数组）虽然能防止主串回溯，但在某些极端情况下，模式串的回溯仍然可能发生多次无效比较。

缺陷示例：

假设模式串 T="aaaaab"，其 LPS 数组为 [0,1,2,3,4,0]。

现在主串 $S$ 正在匹配，在 $T[5]=\text{'b'}$ 处失败（假设 $S[i]=\text{'c'}$）。

1. 匹配失败于 $j=5$.

2. 回溯到 $j = LPS[4] = 4$. ($T[4]=\text{'a'}$)

3. 比较 $S[i]=\text{'c'}$ 和 $T[4]=\text{'a'}$。失败！ (无效比较：$S[i]$ 仍然是一个新的不匹配字符，它不可能与 $T[4]$ 匹配，因为 $T[4]$ 和 $T[5]$ 字符相同都是 'a'，而 $T[5]$ 已经失败了)

4. 回溯到 $j = LPS[3] = 3$. ($T[3]=\text{'a'}$)

5. 比较 $S[i]=\text{'c'}$ 和 $T[3]=\text{'a'}$。失败！

6. ...直到 $j=0$ 失败。

这种情况下，每次回溯到的字符都与原失败字符 $T[5]$ 相同（都是 'a'），导致一系列冗余且注定失败的比较。

2. LPS 的优化数组（$nextval$ 数组）

优化数组（$nextval$ 数组） 的目标是消除这种冗余的比较。

定义：

对于 T 中的任何位置 j，nextval[j] 存储的是：

1. 如果 $T[j] \ne T[nextval[j]]$，则 $nextval[j] = LPS[j]$ (即标准回溯位置)。

2. 如果 $T[j] = T[nextval[j]]$，则 $nextval[j] = nextval[nextval[j]]$ (继续回溯，直到找到一个与 $T[j]$ 不同的字符位置 $k$)。

优化后的回溯逻辑：

当匹配在 T[j] 处失败时，模式串直接回溯到 T[nextval[j]] 处继续匹配。由于 T[nextval[j]]=T[j]，可以确保回溯后的第一次比较不是冗余的。

3. 示例：$T = \text{"aaaaab"}$ 的 $nextval$

T=a a a a a b

LPS=[0,1,2,3,4,0]

最终 $nextval$ 数组 (为简化，通常 $nextval[0]$ 设为 0)： $[0, 0, 0, 0, 0, 0]$

优化后的回溯：

在 T[5]=’b’ 处失败，回溯到 j=nextval[5]=0.

直接比较 S[i]=’c’ 和 T[0]=’a’。只有一次比较，大大减少了冗余操作。

简而言之，LPS 的优化数组（$nextval$ 数组）就是通过跳过那些与失败字符相同的公共前后缀，来提高 KMP 算法的实际执行效率。

！从KMP算法的实际使用角度来看，LPS数组的最后一位在模式匹配过程中确实不会被用到。

原因分析：

在KMP算法中，当我们在位置 j 匹配失败时：

• 我们会跳转到 j = lps[j-1]
• 也就是说，我们用的是 lps[j-1] 而不是 lps[j]

由于 j 的最大值是 m-1（m是模式串长度），所以：

• 当 j = m-1 时，匹配失败会跳转到 lps[m-2]
• 永远不会访问 lps[m-1]

但是 LPS 数组的最后一位仍然有其他用途：

1. 构建LPS数组本身：在计算LPS数组时，需要计算每一位（包括最后一位）
2. 判断周期性：LPS的最后一位可以用来判断字符串的周期性
   • 如果 lps[m-1] > 0 且 m % (m - lps[m-1]) == 0，说明字符串有周期
   • 例如："abababab" 的 LPS 最后一位是 6，可以判断出它有周期"ab"
3. 其他字符串算法：在某些扩展应用中可能会用到

总结：你的理解是正确的！在标准的KMP模式匹配中，LPS数组的最后一位不会在匹配过程中被访问到。

让我检查一下 "ababaaababaa" 是否满足周期性条件：

检查条件：

• 字符串长度 m = 12
• LPS[11] = 1
• 条件1：lps[m-1] > 0 ✓ (1 > 0)
• 条件2：m % (m - lps[m-1]) == 0
  • 即：12 % (12 - 1) == 0
  • 即：12 % 11 == 0 ✗ (结果是1，不是0)

结论：不适用！"ababaaababaa" 不满足周期性条件。

为什么？ 这个字符串确实不是周期性的。让我们看看：

• 如果有周期，周期长度应该是 m - lps[m-1] = 12 - 1 = 11
• 但 11 不能整除 12，所以这个字符串不是由某个子串重复构成的

周期性的例子：

• "ababab"：m=6, lps[5]=4, 6%(6-4)=0 ✓，周期是"ab"
• "abcabcabc"：m=9, lps[8]=6, 9%(9-6)=0 ✓，周期是"abc"

所以你的质疑是对的！我之前举的判断周期性的方法需要同时满足两个条件，而 "ababaaababaa" 只满足第一个条件，不满足第二个，因此它不是周期性字符串。