CS136 Study Guide - Rule 21, Lookup Table, Trie
Document Summary
Diagrams for running of each, where mismatches are signi ed by moving down a level: Boyer moore: idea: run the location search as normal but check for mismatches backwards. Sometimes on a mismatch we can discard everything before the mismatch location. Bm (typical) b b b b a b b b b b b a a a (cid:88) a a . Note: only 5 comparisons, even smaller than n = 12. In the worst case, still requires (n) comparisons. There"s no getting around that, for example, if p = t you have to look at every character of input to verify there are no mismatches. But in some cases you can determine no match exists with signi cantly less than n compares. Two possible rules that can be applied (one considers the mismatch, one considers the matched portion): 1: bad character rule: say mismatch on character c in the text.
