Knuth-Morris-Pratt algorithm string comparison

Question

Construct a pattern of length 8, over the alphabet a, b, such that the number of comparisons in Knuth-Morris-Pratt Algorithm is as large as possible.

I don't quite understand how to start this question, any tips ?

Answer 1

The antilogarithm searches a string for matches to a key, once it matches a character of the string to the first character of the key, it begins comparing the next character of the string, and if that matches, then it compares the next, and so on until it fails.

So the way to maximize comparisons is to not only have the algorithm fail just before finding a match, but to also hide partial matches within such a string so that it has to also consider that partial match after it fails.

For example, given the key "ABABCDB" we could use the following: $$ABABABAB$$

Here it will compare the first four characters $ABAB$, then it will go back and start at the second $A$ and compare $ABAB$ again, then the third, and so on. It will compare fail on each turn after $$ABAB \\ ABAB \\ ABAB \\AB$$

So in this case, we have $14$ comparisons.

Hope that helps.

Answer 2

I cannot comment because I have a new account so please forgive my bad etiquette, but as a member of the same class I believe the answer above is slightly off. To clarify the pattern or key should be some pattern of length 8 containing a or b only e.g. abababab.

The answer above treats this pattern as a string we would search for a key in. But the question is in fact asking the opposite, what key (made up of ab) would maximise the number of comparisons possible for some undisclosed string (of undisclosed length, also made up of only a and b).

I do believe the answer is on to something, and the crux is we want our key such that it makes the smallest possible shifts across the string at each failure when comparing to our imaginary string - which should maximise comparisons.

I am yet to fully solve this myself, but I think the answer lies in the failure function.

I hope it isn't minded that I piggyback off this question rather than just submit the same one. At the very least to save my classmate from posting the wrong answer.