xerox CSL-76-1 A Fast String Searching Algorithm free download

File name CSL-76-1_A_Fast_String_Searching_Algorithm.pdf

A FAST STRING SEARCHING ALGORITHM BY ROBERT S. BOYER* AND J STROTHER MOORE** CSL-76-1 JULY, 1976 An Algori thm is presented that searches for the location, i, of the first occurrence of a character string, pat, in another string, string. During the search operation, the characters of pat are matched starting wi t.h the last character of pat. The informa t i on gained by starti ng t he rna teh a t the end of the pa tterll often a llows the algorithm to proceed in largt~ jumps through the text being searched. Thus, the algori thm has the ullusual property that, in most cases, not all of the first i characters of string are inspected. The number of characters actually inspected (on the average) decreases as a function of the length of pat. For a random English pattern of length 5, the algori thm wi 11 typically inspect if 4 characters of string before finding a match at i. Furthermore, the algorithm has been implemented so that (on the average) fewer than i+patlen machine instructions are executed. These conclusions are supported with empirical evidence and a theoretical analysis of the average behavior of the algori thm. The worst case behavior of the algori thm is linear in i+patlen, assumi ng the availabili ty of array space for tables linear in patlen plus the size of the alphabet. KEY wonns bihliographic search, computational complexity, information retrieval, linear time bound, pa ttern matching, text-edi ting cn CATEGORIES 3.74, 4.40, 5.25 *Computer Science Group, Stanford Hesearch Institute, Menlo Park, Ca. 94025. This work was partially supported by ONU Contract N00014-75-C-OBIB. **Formerly at the Computer Science Laboratory, Xerox Palo Alto Research Center, Palo Alto, Ca 94304, currently at Computer Science Group, Stanford Research Institute, Menlo Park, Ca 94025.\ Introduction Suppose that pat is a string of length patlen and we wish to find the position, i, of the leftmost character in the first occurrence of pat in some string string: pat: AT-THAT string: WHICH-FINALLY-IIALTS.--AT-TIIAT-POINT i: t The obvious search algorithm considers each character position of string and determines whether the successive patlen characters of string starting at that position match the successive patlen characters of pat. Knuth, Morris, and Pratt [4] have observed that this algorithm is quadratic. That is, in the worst case, the number of comparisons is on the order of i*patlen 1. Knuth, Morris, and Pratt have described a linear search algorithm which preprocesses pat in time linear in patlen and then searches string in time linear in i+patlen. In particular, their algorithm inspects each of the first i+patlen-l characters of string precisely once. We now present a search algorithm which is usually