string search frequently encountered kind of search is the so-called string search it is characterized as follows given an array of elements and an array of elementswhere ndeclared as sarray of item parray of item string search is the task of finding the first occurrence of in typicallythe items are charactersthen may be regarded as text and as pattern or wordand we wish to find the first occurrence of the word in the text this operation is basic to every text processing systemand there is obvious interest in finding an efficient algorithm for this task specific feature of this problem is the presence of two arrays and necessity to scan them simultaneously in such way that the coordination of the two indices used to scan the arrays is determined by the data correct implementation of such "braidedloops is simplified by expressing them using the so-called dijkstra' loopi multibranch version of the while loop this fundamental and powerful control structure is described in appendix we consider three string search algorithmsstraight string searchan optimization of the straight search due to knuthmorris and pratt,andfinallythe algorithm of boyer and moor based on revision of the basic idea of the straight searchwhich proves to be the most efficient of the three straight string search before paying particular attention to efficiencyhoweverlet us first present straightforward searching algorithm we shall call it straight string search it is convenient to have in view fig that schematically pictures the pattern of length being matched against the text of length in position the index numbers the elements of the patternand the pattern element [jis matched against the text element [ + - string pattern - fig pattern of length is being matched against text of length in position the predicate (ithat describes complete match of the pattern against text characters in position is formulated as followsr(iaj < pj si+ the allowed values of where match can occur range from to - inclusive is evaluated by repeatedly comparing the corresponding pairs of characters thisevidentlyamounts to linear search of non-matching pairr( (aj < pj si+ ~(ej < pj si+jtherefore (iis easily formulated as followsprocedure (iinteger)booleanvar jintegerbegin ( < * :