Pattern prefix-function computation in Knuth-Morris-Pratt Algorithm
-
26-05-2021 - |
Pregunta
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.
Solución
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
Otros consejos
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
- first symbol arbitrary, say a
- second symbol must be different from first, or the prefix length would be 1
- third must be the same as first
- fourth must be the same as second
- fifth must be the same as third
- can be neither of the two symbols used so far, a would give a prefix length of 1, b of 4
- seventh must be first
- must be second
- must be third
- must be fourth
- must be fifth
- 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
.