vendredi 3 janvier 2020

Problem with finding pattern for Knuth Morris Pratt algorithm

I have a problem finding the correct failure links for the pattern P = abacaaba using Knuth-Morris-Pratt.

This is what i have got so far:

k 1 2 3 4 5 6 7 8

P(k) a b a c a a b a

FLink(k) 0 0 1 0 1 1 1 1

  1. The first one is always 0
  2. Now we have k(i) = a1 and k(j) = b2, these are a mismatch, so it should be 0
  3. Now we have k(i) = a1 and k(j) = a3, these are a match, a1 = 0, so a3 = 0 + 1 = 1
  4. Now we jump i and j one to the right, k(i) = b2 and k(j) = c4, these are a mismatch, so we jump i back 1. Now k(i) = a1 and this is a mismatch. We can't go back any further, so c4 = 0
  5. Now k(i) = a1 and k(j) = a5, these are a match. The value of a1 is 0, so a5 = 0 + 1 = 1.
  6. We put i and j one to the right again. k(i) = b2 and k(j) = a6. This is a mismatch. We put back i by 1, so k(i) = a1. a1 and a6 are a match and the value of a1 is 0, so a6 = 0 + 1 = 1.
  7. We put i and j one to the right again. k(i) = b2 and k(j) = b7. These are a match and the value of b2 is 0, so the value of b7 will be 0 + 1 = 1.
  8. Finally k(i) = b2 and k(j) = a8. These are not a match, the new k(i) will be a1. a1 and a8 are a match and the value of i is 0, so a8 = 0 + 1 = 1.

The answer that my teacher gives for FLink(k) is 0 1 1 2 1 2 2 3. Am i doing something completely wrong?

Aucun commentaire:

Enregistrer un commentaire