evidently the condition ( -ddq( -dmust hold before assigning :dif the invariant (ijjq( -jis to hold thereafter this precondition is therefore our guideline for finding an appropriate expression for along with the condition ( -jjq( - )which is assumed to hold prior to the assignment (all subsequent reasoning concerns this point of the programthe key observation is that thanks to ( -jjwe know that pj- si- si- (we had just scanned the first characters of the pattern and found them to matchtherefore the condition ( -ddwith ji pd- si- si- translates into an equation for dp pd- pj- pj- as to ( - )this condition follows from ( -jprovided ~ ( -kfor + the validity of ~ ( -kfor is guaranteed by the inequality [ip[jalthough the conditions ~ ( - ~ (ikmfor + - cannot be evaluated from the scanned text fragment onlyone can evaluate the sufficient conditions ~ ( - ,kexpanding them and taking into account the already found matches between the elements of and pwe obtain the following conditionp pk- pj- pj- for all + - that isd must be the maximal solution of the above equation fig illustrates the function of examples , string pattern shifted pattern = = (max shift = - = , = = (max shift = - = , = = (max shift = - = fig partial pattern matches and computation of if there is no solution for dthen there is no match in positions below + then we set :- such situation is shown in the upper part in fig the last example in fig suggests that we can do even slightly betterhad the character pj been an instead of an fwe would know that the corresponding string character could not possibly be an aand the shift of the pattern with - had to be performed in the next loop iteration (see fig the lower