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

Question

所以对于下面的子串

1 2 3 4 5 6 7 8 9 10 11

a b c d a b c d a b  x

什么是前缀函数？我和我的一个 friend 计算了它，我们得到了不同的结果，我的是:

a b c d a b c d a b x

0 0 0 0 1 2 3 4 5 6 2

和他的:

a b c d a b c d a b x

0 0 0 0 1 2 3 4 1 2 0

如果我错了，那是为什么？

Answer 1

前缀表应该是:

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

所以给出的两个版本都不正确。

对于你的表的最后一个条目

a b c d a b c d a b x
0 0 0 0 1 2 3 4 5 6 2
                    ^
                    |
                this one

要正确，a b c d a b c d a b x 的长度为 2 的后缀 b x 也必须是其长度为 2 的前缀，即 a b 相反。

如果前缀表中的条目不为零，则相应的前缀和后缀已在下表中标记:

a                       0
a b                     0
a b c                   0
a b c d                 0

a  b c d a              1
-
         =
a b c d a b             2
---
        ===

a b c d a b c           3
-----
        =====

a b c d a b c d         4
-------
        =======

a b c d a b c d a       5
---------
        =========

a b c d a b c d a b     6
-----------
        ===========

a b c d a b c d a b  x   0