while ( ( < ( [ - [ - ]do dec( )dec(jelsif ( ( <ndo : [ord( [ - ])] :mk :iend the indices satisfy < <mm <ii < thereforetermination with implies ( ( ) match at position - termination with demands that nhence (iimplies ( )signalling that no match exists of course we still have to convince ourselves that (iand (ijare indeed invariants of the two repetitions they are trivially satisfied when repetition startssince (mand (xmare always true consider the first branch simultaneously decrementing and does not affect ( )andsince sk pj- had been establishedand (ijholds prior to decrementing jthen (ijholds after it as well in the second branchit is sufficient to show that the statement : ds[ - never falsifies the invariant (ibecause (ijis satisfied automatically after the remaining assignments (iis satisfied after incrementing provided that before the assignment ( +ds[ - ]is guaranteed since we know that (iholdsit suffices to establish ~ ( +hfor ds[ - ]- we now recall that dx is defined as the distance of the rightmost occurrence of in the pattern from the end this is formally expressed as akm-dx < - pk substituting si- for xwe obtain akm-ds[ - < - si- pk ah < <ds[ - ]- si- pm- - ah < <ds[ - ]- ~ ( +hthe following program includes the presentedsimplified boyer-moore strategy in setting similar to that of the preceding kmp-search program procedure search (var sparray of charmnintegervar rinteger)(adens _bm *(*search for pattern of length in text of length *(*if is foundthen indicates the position in sotherwise - *var ijkintegerdarray of integerbegin for : to do [ : endfor : to - do [ord( [ ]): - - endi :mj :mk :iwhile ( ( < ( [ - [ - ]do dec( )dec(jelsif ( ( <ndo : [ord( [ - ])] :mk :iendif < then : else :- end end search analysis of boyer-moore search the original publication of this algorithm [ - contains detailed analysis of its performance the remarkable property is that in all except especially construed cases it requires substantially less than comparisons in the luckiest casewhere the last character of the pattern always hits an unequal character of the textthe number of comparisons is /