Search code examples
stringalgorithmsubstringknuth-morris-pratt

Pattern prefix-function computation in Knuth-Morris-Pratt Algorithm

Is there any possibility in the prefix-function of a given pattern to have something like this,

0 0 1 2 3 0 1 2 3 4 5 3 4 5 6 7 0 1 2

In the above prefix function after 4 5 is there only possibility of either 6 or 0? If there is a possibility for e.g 3(less than 5 and greater than 0) after 4 5 as in the above one then how the pattern should be.

I can think of patterns only similar to this one,

a b a b a b a b c a 
0 0 1 2 3 4 5 6 0 1

Thanks.

Solution

  • Here is an example pattern where you have fail link 4 after 6:

    a b c a b c d a b c a b c a
0 0 0 1 2 3 0 1 2 3 4 5 6 4