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

哪个是前缀函数?我和我的一个朋友计算了一下，我们得到了不同的结果，我的是:

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

Answer 2

java中的KMP函数:

public int[] KMP(String val) {
    int i = 0;
    int j = -1;
    int[] result = new int[val.length() + 1];
    result[0] = -1;
    while (i < val.length()) {
        while (j >= 0 && val.charAt(j) != val.charAt(i)) {
            j = result[j];
        }
        j++;
        i++;
        result[i] = j;
    }
    return result;
}

前缀数组的结果:

[-1, 0, 0, 0, 0, 1, 2, 3, 4, 5, 6, 0]

Answer 3

你们两个答案都不对。前缀函数或部分匹配表如下:

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

你的答案是正确的，直到索引10。但在最后一个指标中，你做错了。部分匹配表的索引11的值为0的原因是因为没有合适的前缀匹配到索引11的字符串的任何合适的后缀。因为在这个位置的所有适当后缀都以x结尾，而在这个位置的任何适当前缀都不会以x结尾。

如果你在理解前缀函数或部分索引表的含义上有问题，你可以看看这个文档。它有一个很好的解释。

Answer 4

你的两个答案都错了。正确的是

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