Accession Number : AD0773138

Title :   String-Matching and Other Products.

Descriptive Note : Technical memo.,

Corporate Author : MASSACHUSETTS INST OF TECH CAMBRIDGE PROJECT MAC

Personal Author(s) : Fischer,Michael J. ; Paterson,Michael S.

Report Date : JAN 1974

Pagination or Media Count : 23

Abstract : The string-matching problem considered is to find all occurrences of a given pattern as a substring of another longer string. When the pattern is simply a given string of symbols, there is an algorithm due to Morris, Knuth and Pratt which has a running time proportional to the total length of the pattern and long string together. This time may be achieved even on a Turing machine. The more difficult case where either string may have don't care symbols which are deemed to match with all symbols is also considered. By exploiting the formal similarity of string-matching with integer multiplication, a new algorithm has been obtained with a running time which is only slightly worse than linear. (Author)

Descriptors :   *Computations, *Computer programming, *Boolean algebra, Algorithms

Subject Categories : Theoretical Mathematics
      Computer Programming and Software

Distribution Statement : APPROVED FOR PUBLIC RELEASE