3

给定一个模式abababc，前缀表是[0,0,1,2,3,4,0]。但是， at 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 |        | 
+---+----------+-------+--------+

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

4

1 回答 1

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。

于 2018-07-28T15:08:58.330 回答