makes sensei preserves the invariant for the first branch it is the condition ( <nm( (si+ pjwhich guarantees (ijafter is incremented for the second branchthe last operand of this conjunction must have inequality instead of equalitywhich would imply ~ (iand guarantee (iafter is incremented taking into account that the two guards are evaluated in their textual orderthe last operand of the conjunction can be dropped in the second branchand one arrives at the following programi : : (adens _straight *while ( < - ( ( [ +jp[ ]do incj elsif ( < - ( mdo inci ) : end after the loop terminatesthe condition is guaranteed to holdwhich is equal to conjuncttion of negations of all quardsi ( -mor ( >mmoreoverfrom the structure of the loop it follows that the two operands cannot hold simultanelouslyand cannot exceed then - means that there is no match anywhere in the textwhereas mthat (ip(imis truei complete match is found in position analysis of straight string search this algorithm operates quite effectivelyif we can assume that mismatch between character pairs occurs after at most few comparisons in the inner loop this is likely to be the caseif the cardinality of the item type is large for text searches with character set size of we may well assume that mismatch occurs after inspecting or characters only neverthelessthe worst case performance is rather alarming considerfor examplethat the string consist of - ' followed by single band that the pattern consist of - ' followed by then in the order of * comparisons are necessary to find the match at the end of the string as we shall subsequently seethere fortunately exist methods that drastically improve this worst case behaviour the knuth-morris-pratt string search around knuthj morrisand pratt invented an algorithm that requires essentially in the order of character comparisons onlyeven in the worst case [ - the new algorithm is based on the observation that by starting the next pattern comparison at its beginning each timewe may be discarding valuable information gathered during previous comparisons after partial match of the beginning of the pattern with corresponding characters in the stringwe indeed know the last part of the stringand perhaps could have precompiled some data (from the patternwhich could be used for more rapid advance in the text string the following example of search for the word hooligan illustrates the principle of the algorithm underlined characters are those which were compared note that each time two compared characters do not matchthe pattern is shifted all the waybecause smaller shift could not possibly lead to full match hoola-hoola girls like hooligans hooligan hooligan hooligan hooligan hooligan hooligan hooligan in contrast with the simple algorithmhere the comparison point (the position of the text element being compared with some element of the patternis never moved backwards this suggests that we must abandon the notion that always marks the current position of the first pattern character in the text rather