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
aabaababb

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(同样的情况)