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
- The first one is always 0
- Now we have k(i) = a1 and k(j) = b2, these are a mismatch, so it should be 0
- Now we have k(i) = a1 and k(j) = a3, these are a match, a1 = 0, so a3 = 0 + 1 = 1
- 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
- Now k(i) = a1 and k(j) = a5, these are a match. The value of a1 is 0, so a5 = 0 + 1 = 1.
- 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.
- 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.
- 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