KMP failure function calculation

Question

My professor solved the kmp failure function as follows:

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

From other texts I checked online, I found out it might be wrong, I went back to confirm from him again and he told me he's absolutely right. Can someone pls explain to me why he thinks it's right or wrong in a simple step by step manner? Thanks

Answer 1

As I understand the algorithm, the failure function for your example should be the following:

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 - failure function (by definition, this is the length of the longest prefix of the string which is a suffix also)

Here how I built it step by step:

f(a) = 0 (always = 0 for one letter)

f(aa) = 1 (one letter 'a' is both a prefix and suffix)

f(aab) = 0 (there is no the same suffixes and prefixes: a != b, aa != ab)

f(aaba) = 1 ('a' is the same in the beginning and the end, but if you take 2 letters, they won't be equal: aa != ba)

f(aabaa) = 2 ( you can take 'aa' but no more: aab != baa)

f(aabaab) = 3 ( you can take 'aab')

f(aabaaba) = 4 ( you can take 'aaba')

f(aabaabab) = 0 ( 'a' != 'b', 'aa' != 'ab' and so on, it can't be = 5, so as 'aabaa' != 'aabab')

f(aabaababb) = 0 ( the same situation)

Answer 2

Since @user1041889 was confused (and got me confused too) I'll lay here the differences between the Z-function and the failure function.

Failure function, π[i]:

Is the mapping of and index to the length of the longest prefix of the string which is also a suffix

But that's arguably Chinese so I'll dumb it down in order to actually understand what I'm saying:

How big is the longest sub-string at the beginning of the string of interest, that is equal to the sub-string ending at index i

Or equivalently:

What is the length of the biggest sub-string ending at index i which matches the start of the string of interest

So in your example:

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

We observe that π[6] = 3, so what's the substring that ends at index 6 with length 3? aab!

Interesting how we've seen that before!

Let's check that it is indeed the biggest one: baab != aab. Yup!

Notice how this implies that the failure functions always grows uniformly.

That isn't the case for the Z-algorithm.

[SAVING DRAFT to continue later]