KMP失效函数计算

Question

我的教授解决了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

从我在网上查看的其他文本中，我发现这可能是错误的，我再次回去向他确认，他告诉我他绝对正确。有没有人可以简单地一步一步地给我解释一下为什么他认为这是对的或错的？谢谢

Answer 1

根据我对算法的理解，您的示例的失败函数应该如下所示：

1 2 3 4 5 6 7 8 9

A a b a a b 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(aabaababb) =0(相同情况)

Answer 2

由于@user1041889被弄糊涂了(也把我弄糊涂了)，我将在这里介绍Z函数和失败函数之间的区别。

故障函数，π[i]

是和索引到字符串的最长前缀长度的映射，该前缀也是后缀

但这可以说是中文的，所以为了真正理解我在说什么，我把它简化了：

在感兴趣的字符串的开头的最长的子串有多大，即等于在索引i处结束的子串

或者等效地：

在索引i处结束的与感兴趣字符串的开头匹配的最大子字符串的长度是多少

因此，在您的示例中：

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算法的情况。

保存草稿以在以后继续