while ( ( [ip[ ]do : [ ]elsif ( ( ndo inc( )inc( )endif then : - else :- end end search analysis of kmp search the exact analysis of the performance of kmp-search islike the algorithm itselfvery intricate in [ - its inventors prove that the number of character comparisons is in the order of +nwhich suggests substantial improvement over * for the straight search they also point out the welcome property that the scanning pointer never backs upwhereas in straight string search the scan always begins at the first pattern character after mismatchand therefore may involve characters that had actually been scanned already this may cause awkward problems when the string is read from secondary storage where backing up is costly even when the input is bufferedthe pattern may be such that the backing up extends beyond the buffer contents the boyer-moore string search the clever scheme of the kmp-search yields genuine benefits only if mismatch was preceded by partial match of some length only in this case is the pattern shift increased to more than unfortunatelythis is the exception rather than the rulematches occur much more seldom than mismatches therefore the gain in using the kmp strategy is marginal in most cases of normal text searching the method to be discussed here does indeed not only improve performance in the worst casebut also in the average case it was invented by boyer and moore around and we shall call it bm search we shall here present simplified version of bm-search before proceeding to the one given by boyer and moore bm-search is based on the unconventional idea to start comparing characters at the end of the pattern rather than at the beginning like in the case of kmp-searchthe pattern is precompiled into table before the actual search starts letfor every character in the character setdx be the distance of the rightmost occurrence of in the pattern from its end now assume that mismatch between string and pattern was discovered then the pattern can immediately be shifted to the right by dp[ - positionsan amount that is quite likely to be greater than if pm- does not occur in the pattern at allthe shift is even greaternamely equal to the entire pattern' length the following example illustrates this process hoola-hoola girls like hooligans hooligan hooligan hooligan hooligan hooligan since individual character comparisons now proceed from right to leftthe followingslightly modified versions of of the predicates pr and are more convenient (ijakj < si- + pk (ip( (iakm < ~ (kthe loop invariant has the form (ip(ijit is convenient to define - + then the bm-algorithm can be formulated as follows :mj :mk :