string - Knuth-Morris-Pratt 算法中的模式前缀函数计算

Question

给定模式的前缀功能是否有可能具有这样的东西，

0 0 1 2 3 0 1 2 3 4 5 3 4 56 7 0 1 2

在 4 5 之后的上述前缀函数中，是否只有 6 或 0 的可能性？如果在 4 5 之后有可能出现例如 3（小于 5 且大于 0），如上述那样，那么模式应该如何。

我只能想到类似于这个的模式，

a b a b a b a b c a 
0 0 1 2 3 4 5 6 0 1

谢谢。

Answer 1

这是一个示例模式，其中 6 后链接 4 失败：

a b c a b c d a b c a b c a
0 0 0 1 2 3 0 1 2 3 4 5 6 4

Answer 2

您的特定示例是不可能的。当您开始从所需的前缀表构造字符串时，您会得到

0 0 1 2 3 0 1 2 3 4 5 3 4 5 6 7 0 1 2
a b a b a c a b a b a

1. 第一个符号是任意的，比如说 a
2. 第二个符号必须与第一个不同，否则前缀长度为 1
3. 第三个必须与第一个相同
4. 第四个必须与第二个相同
5. 第五个必须与第三个相同
6. 不能是目前使用的两个符号中的任何一个，a 将给出前缀长度 1，b 为 4
7. 第七必须是第一
8. 必须是第二
9. 必须是第三
10. 必须是第四
11. 必须是第五
12. a 会给出前缀长度 1，b 会给出 4，c 会给出 6，其他的都会给出 0

表中对应于长度前缀的条目p给出了该前缀的最宽边框的宽度b，例如w。下一个条目只能是w+1（如果b是可扩展的）、0（如果没有前缀匹配）或比b.

因此，如果table[p]包含 length-p 前缀的最宽边框的宽度（带有table[0] = -1），table[p+1]则为1+table[p], 1+table[table[p]], ...,之一1+table[table[...[table[p]]]] = 1 + table[0] = 0。