CODEWITHSUNDEEP
algorithmsubstringknuth-morris-pratt
user3848412
user3848412

Reputation: 109

Prefix-function computation in Knuth-Morris-Pratt Algorithm

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?

Upvotes: 2

Views: 1611

Answers (4)

mikyra
mikyra

Reputation: 10367

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

Upvotes: 1

Buraira Nasir
Buraira Nasir

Reputation: 31

both of your answers are wrong. correct one will be 

a b c d a b c d a b x

0 0 0 0 1 2 3 4 5 6 0

Upvotes: 1

taufique
taufique

Reputation: 2751

Neither of your answers are correct. The prefix function or partial match table would be the following:

a b c d a b c d a b x

0 0 0 0 1 2 3 4 5 6 0

Your answer was correct upto index 10. But in the last index you have done something wrong. The reason why value of index 11 of partial match table would 0 is because there are no proper prefix which matches any proper suffix of the string upto index 11. Because all proper suffixes at this position will end with x and no proper prefix at this position will end with x.

If you have problem understanding what actually prefix function or partial index table means you can take a look into this document. It has a very good explanation. Hope it helps.

Upvotes: 1

Pham Trung
Pham Trung

Reputation: 11284

My KMP function in java:

public int[] KMP(String val) {
    int i = 0;
    int j = -1;
    int[] result = new int[val.length() + 1];
    result[0] = -1;
    while (i < val.length()) {
        while (j >= 0 && val.charAt(j) != val.charAt(i)) {
            j = result[j];
        }
        j++;
        i++;
        result[i] = j;
    }
    return result;

}

Result for prefix arrays:

[-1, 0, 0, 0, 0, 1, 2, 3, 4, 5, 6, 0]

Upvotes: 1

Related Questions