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

Question

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.

Answer 1

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

Answer 2

Your particular example is impossible. When you start constructing a string from the desired prefix table, you get

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

1. first symbol arbitrary, say a
2. second symbol must be different from first, or the prefix length would be 1
3. third must be the same as first
4. fourth must be the same as second
5. fifth must be the same as third
6. can be neither of the two symbols used so far, a would give a prefix length of 1, b of 4
7. seventh must be first
8. must be second
9. must be third
10. must be fourth
11. must be fifth
12. a would give a prefix length of 1, b would give 4, c would give 6, everything else gives 0

The entry in the table corresponding to the prefix of length p gives the width of the widest border b of that prefix, say w. The next entry can only be w+1 (if b is extensible), 0 (if no prefix matches), or one more than the width of some border of b.

So if table[p] contains the width of the widest border of the length-p prefix (with table[0] = -1), then table[p+1] is one of 1+table[p], 1+table[table[p]], ..., 1+table[table[...[table[p]]]] = 1 + table[0] = 0.