算法 - KMP 前缀 table：是否有可能有两个选择跳转到？

Question

给定一个模式 abababc，前缀 table 是 [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

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

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

(i, j) 的值随着每次迭代按字典顺序递增。
0 ≤ j - i ≤ len(pattern)，即 window 有效且永远不会长于模式。
如果模式出现在位置i'，则(i, j) ≤lex (i', i' + len(pattern))，其中≤lex表示字典序比较。

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

不变量 2：如果 window 为空，则模式也为空（我们退出），或者 window 增长。如果 window 长度等于模式长度，那么要么 window 包含模式（然后我们退出），要么 window 收缩，因为它不能包含不是模式的前缀模式。否则，那么 window 增长或缩小一个都可以。

与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))，所以这种情况很好。或者，如果当前 window 不是模式的前缀，那么我们推断 i < i'，因为当前 window 无法扩展以包含该模式。因此，我们得出结论 (i + 1, j) <lex (i', i' + len(pattern))，因为 i + 1 ≤ i' 和 j ≤ i + len(pattern) < i' + len(pattern).

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

算法 - KMP 前缀 table：是否有可能有两个选择跳转到？

Algorithm - KMP prefix table: is it possible there are two choices to jump to?

string

algorithm

pattern-matching

nfa

knuth-morris-pratt