我的教授解决了 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
从我在网上查的其他文本中，我发现它可能是错误的，我再次回到他那里确认，他告诉我他完全正确。有人可以向我解释为什么他认为这是对的或错误的一步一步的简单方式吗？谢谢
最佳答案
据我了解该算法，您示例的失败函数应如下所示:
1 2 3 4 5 6 7 8 9
a a b a a b a b b
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(同样的情况)
关于string-matching - KMP失效函数计算，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/16125544/