Can I read A Fast String Searching Algorithm on EtoBox?

A Fast String Searching Algorithm by Robert S. Boyer; J. Strother Moore is a Computer Science article available to read on EtoBox.

What is A Fast String Searching Algorithm about?

An algorithm is presented that searches for the location, “ __i__ l” of the first occurrence of a character string, “ __pat__ ,” in another string, “ __string__ .” During the search operation, the characters of __pat__ are matched starting with the last character of __pat__ . The information gained by starting the match at the end of the pattern often allows the algorithm to proceed in large jumps through the text being searched. Thus the algorithm has the unusual 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 algorithm will typically inspect __i__ /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 algorithm. The worst case behavior of the algorithm is linear in __i__ + __patlen__ , assuming the availability of array sp

Who reads A Fast String Searching Algorithm?

Author

Robert S. Boyer; J. Strother Moore

Publisher

ACM

Published

1977

Language

EN

Field

Computer Science (Physical Sciences)