Search for question
Question

Consider running the Rabin-Karp rolling hash string matching algorithm, except modifying the loop to remove

the explicit verification step -- that is, if texthash=-patternhash, then instead of going into an explicit

verification loop, we simply report that the pattern matches the text.

What is true about the correctness of this algorithm?

Select one:

O a. It is still a correct string matching algorithm, but might be noticeably slower

O b. It can give 'false negatives', i.e., it can miss some occurrences of the pattern, but it will never incorrectly claim

that the pattern occurs in the string

O c. It can give 'false positives', i.e., it can claim matches which are not real, but it will never falsely claim that the

pattern does not occur in the string

O d. It can make errors in both directions (both false positives and false negatives)