Assignment 5 Question 4 Clarification

[cs240]

An oversight has been found the the psuedocode of the KMP algorithm on slide 23 of module 8. The KMP algorithm should terminate when the pattern can not fit in the text, see the newsgroup for clarification. For the purpose of the Assignment, we will accept either way.

[cs240]

Clarification
In reality, the algorithm should terminate if there is not enough
characters left in the text for the pattern to fit.

EG:
T=abbabbabbb
P=abbaba

abbabbabbb
abbaba
mmmmmx
abbaba (STOP)
iiimmx
abbb <- this last check is not performed since P can not fit
into T[6-9]

m are matches, x are mismatches, i are implicit matches

For the purpose of the assignment, we will accept both methods.

[Maros Hluska]

Post by cs240
An oversight has been found the the psuedocode of the KMP algorithm on slide 23 of module 8. The KMP algorithm should terminate when the pattern can not fit in the text, see the newsgroup for clarification. For the purpose of the Assignment, we will accept either way.

What should be changed in the pseudocode? The "while i < n" to "while i
< n - m" ?

Maros Hluska

[Daniel S. Roche]

Post by Maros Hluska
What should be changed in the pseudocode? The "while i < n" to "while i
< n - m" ?

Not quite. In this algorithm, i is the index that we are currently
looking at in the text, so certainly we want to allow i=n-1 for instance
to check the last character of the text against the last character of
the pattern.

Instead, that condition (on line 4, slide 23, module 8) should be
changed to "i < n AND i-j <= n-m". This is because i-j is the guess
index, and valid guesses are from 0 up to n-m inclusive (see slide 17).

Actually, since we know that j < m at any given point, we could simplify
the condition of the while loop to just "n-i >= m-j". But I think this
makes the logic a little less clear.

-Dan Roche
CS 240 Instructor, Section 003