string - 算法-KMP前缀表: is it possible there are two choices to jump to?

Question

给定一个模式abababc，前缀表是[0,0,1,2,3,4,0]。但是，在 ababab 中，abab 和 ab 都是前缀。为什么我们只将 abab 视为有效前缀？

+---+----------+-------+--------+
| i |   P[i]   | 𝝥[i]  | Prefix |
+---+----------+-------+--------+
| 0 | a        |     0 |        |        
| 1 | ab       |     0 |        |        
| 2 | aba      |     1 | a      | 
| 3 | abab     |     2 | ab     | 
| 4 | ababa    |     3 | aba    | 
| 5 | ababab   |     4 | abab   | (notice here ab can also be a prefix)
| 6 | abababc  |     0 |        | 
+---+----------+-------+--------+

我想不出一个例子，其中较长的前缀会失败但较短的前缀会起作用。有没有证据表明应该只考虑最长的前缀？谢谢!

Answer 1

抛开花哨的数据结构，您可以将 KMP 视为在某种程度上类似于以下(极其低效的)算法。

def find(pattern, string):
    i = j = 0
    while j <= len(string):
        if string[i:j] == pattern:
            return True
        if pattern.startswith(string[i:j]):
            j += 1
        else:
            i += 1
    return False

在英语中，我们在字符串上从左到右滑动一个可变长度窗口，如果窗口包含模式则返回 true，否则返回 false。在每一步中，如果窗口包含模式的前缀，那么我们就前进到正确的端点。否则，我们推进左端点。

这个算法显然没有误报。我们通过归纳证明了以下三个不变量，这意味着它终止并且也没有假阴性。

1. (i, j) 的值每次迭代都会按字典顺序增加。

2. 0 ≤ j - i ≤ len(pattern) ，即窗口有效且永远不会长于模式。

3. 如果模式出现在位置 i' , 然后 (i, j) ≤lex (i', i' + len(pattern)) , 其中≤lex表示字典序比较。

不变量 1:在每次迭代中，i或 j递增。

不变量 2:如果窗口为空，则模式也为空(我们退出)，或者窗口变大。如果窗口长度等于模式长度，那么要么窗口包含模式(然后我们退出)，要么窗口缩小，因为它不能包含不是模式的模式前缀。否则，窗口增大或缩小一个都没有问题。

与 while 循环的退出条件一起，不变量 1 和 2 意味着终止，因为算法状态转换形成有限有向无环图。

不变量 3:如果 (i, j) = (i', i' + len(pattern)) ，然后我们找到了模式(并退出)，所以假设 (i, j) <lex (i', i' + len(pattern)) .自 (i, j + 1)是(i, j)的后继者按字典顺序，我们知道(i, j + 1) ≤lex (i', i' + len(pattern)) ，所以这种情况很好。或者，如果当前窗口不是模式的前缀，那么我们推断 i < i' ，因为当前窗口无法扩展以包含该模式。因此，我们得出结论 (i + 1, j) <lex (i', i' + len(pattern)) , 自 i + 1 ≤ i'和 j ≤ i + len(pattern) < i' + len(pattern) .

---

将此与 KMP 联系起来，前缀表的使用方式是递增 i直到 string[i:j]又是模式的前缀。使用最长的前缀意味着我们不会跳过 i 的值.跳过可能会破坏不变量 3。