text processing another occurrence the efficiency of the boyer-moore algorithm relies on creating lookup table that quickly determines where mismatched character occurs elsewhere in the pattern in particularwe define function last(cas if is in plast(cis the index of the last (rightmostoccurrence of in otherwisewe conventionally define last( - if we assume that the alphabet is of fixedfinite sizeand that characters can be converted to indices of an array (for exampleby using their character code)the last function can be easily implemented as lookup table with worst-case ( )time access to the value last(choweverthe table would have length equal to the size of the alphabet (rather than the size of the pattern)and time would be required to initialize the entire table we prefer to use hash table to represent the last functionwith only those characters from the pattern occurring in the structure the space usage for this approach is proportional to the number of distinct alphabet symbols that occur in the patternand thus (mthe expected lookup time remains independent of the problem (although the worst-case bound is ( )our complete implementation of the boyer-moore pattern-matching algorithm is given in code fragment def find boyer moore(tp) """return the lowest index of at which substring begins (or else - "" nm len( )len(pintroduce convenient notations if = return trivial search for empty string last build 'lastdictionary for in range( ) lastp[kk later occurrence overwrites align end of pattern at index - of text - an index into - an index into while if [ = [ ] matching character if = return pattern begins at index of text else - examine previous character - of both and else last get( [ ]- last( [ ]is - if not found + min(kj case analysis for jump step = - restart at end of pattern return - code fragment an implementation of the boyer-moore algorithm