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

Question

在给定模式的前缀函数中有没有可能有这样的东西，

0 0 1 2 3 0 1 2 3 4 5 3 4 5 6 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

以下是一个示例模式，其中链路4在6之后出现故障：

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. 第一个符号任意，例如
2. 第二个符号必须不同于第一个，或者前缀长度必须为1
3. 第三个必须与第一个

相同<>H110第五个必须与第三个相同H211

1. 不能是到目前为止使用的两个符号中的任何一个，a将给出前缀长度1，b的4个

H114第七个必须是第一个H215H116必须是第二个H217

1. 必须是第三个
2. 必须是第四个
3. 必须是第五个
4. 必须是第二个H219
5. 必须是第四个
6. 必须是第五个
7. 必须是第二个H217H118必须是第三个H219
8. 必须是第四个
9. 必须是第五个
10. 必须是第五个
11. 必须是第三个
12. 必须是第四个
13. 必须是第五C会给6，其他的都会给0

表中与长度为p的前缀相对应的条目给出了该前缀的最宽边界b的宽度，例如w。下一个条目只能是w+1 (如果b是可扩展的)、0(如果没有匹配的前缀)，或者比b的某个边框的宽度大1。

因此，如果table[p]包含长度为-p前缀的最宽边框的宽度(带有table[0] = -1)，则table[p+1]是1+table[p]、1+table[table[p]]、...、1+table[table[...[table[p]]]] = 1 + table[0] = 0之一。