So for the following sub string
1 2 3 4 5 6 7 8 9 10 11
a b c d a b c d a b x
Which is the prefix function? Me and one of my friends computed it and we have different results, mine is:
a b c d a b c d a b x
0 0 0 0 1 2 3 4 5 6 2
and his:
a b c d a b c d a b x
0 0 0 0 1 2 3 4 1 2 0
If I am wrong, why is that?
The prefix table should be:
a b c d a b c d a b x
0 0 0 0 1 2 3 4 5 6 0
so both versions given are not right.
For the last entry of your table
a b c d a b c d a b x
0 0 0 0 1 2 3 4 5 6 2
^
|
this one
to be correct, the suffix of length 2 of a b c d a b c d a b x which is b x would also have to be its length 2 prefix, which is a b instead.
In case of entries different from zero in the prefix table corresponding prefixes and suffixes have been marked in the table below:
a 0
a b 0
a b c 0
a b c d 0
a b c d a 1
-
=
a b c d a b 2
---
===
a b c d a b c 3
-----
=====
a b c d a b c d 4
-------
=======
a b c d a b c d a 5
---------
=========
a b c d a b c d a b 6
-----------
===========
a b c d a b c d a b x 0