我的教授解决了kmp故障功能如下：
index 1 2 3 4 5 6 7 8 9
string a a b a a b a b b
ff 0 1 2 1 2 3 4 5 1
从网上查到的其他文字，我发现可能是错的，我又回去跟他确认，他告诉我他完全正确。有人可以通过简单的逐步方式向我解释为什么他认为这是对还是错？谢谢
问问题
22041 次
2 回答
23
据我了解该算法，您的示例的故障函数应如下所示：
1 2 3 4 5 6 7 8 9
阿拉巴巴
0 1 0 1 2 3 4 0 0
f - 失败函数（根据定义，这是字符串的最长前缀的长度，也是后缀）
这是我如何逐步构建它的：
f(a) = 0（一个字母总是 = 0）
f(aa) = 1（一个字母'a'既是前缀又是后缀）
f(aab) = 0（没有相同的后缀和前缀：a != b, aa != ab）
f(aaba) = 1 （'a' 开头和结尾是一样的，但是如果你取 2 个字母，它们将不相等：aa != ba）
f(aabaa) = 2 （你可以取 'aa' 但不能再取了：aab != baa）
f(aabaab) = 3 (你可以取'aab')
f(aabaaba) = 4 (你可以取'aaba')
f(aabaabab) = 0 ( 'a' != 'b', 'aa' != 'ab' 等等，不可能是 = 5，所以 'aabaa' != 'aabab')
f(aabaabbabb) = 0（同样的情况）
于 2013-06-23T16:33:15.337 回答
1
由于@user1041889 很困惑（也让我很困惑），我将在这里说明 Z 函数和故障函数之间的区别。
失效函数，π[i]：
是字符串最长前缀长度的映射和索引，也是后缀
但这可以说是中文，所以我会把它弄糊涂，以便真正理解我在说什么：
感兴趣的字符串开头的最长子字符串有多大，等于以 index 结尾的子字符串
i
或等效地：
i与感兴趣的字符串的开头匹配的以 index 结尾的最大子字符串的长度是多少
所以在你的例子中：
index 1 2 3 4 5 6 7 8 9
string a a b a a b a b b
ff 0 1 0 1 2 3 4 0 0
我们观察到π[6] = 3，那么以索引 6 结尾且长度为 3 的子字符串是什么？aab！
有趣的是我们以前是怎么看到的！
让我们检查一下它确实是最大的一个：baab != aab. 是的！
注意这意味着失效函数总是均匀增长。
Z 算法并非如此。
[正在保存草稿，稍后继续]
于 2021-03-30T16:59:18.563 回答