KMP failure function calculation
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
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)