Rapid identification of repeated patterns in strings, trees and arrays

Authors:
  • RKRichard M. Karp
    Richard M. Karp
  • RMRaymond E. Miller
    Raymond E. Miller
  • ARArnold L. Rosenberg
    Arnold L. Rosenberg
Open Access
Publisher website
Google Scholar
Abstract
In this paper we look at a number of matching problems and devise general techniques for attacking such problems. In particular, we describe a strategy for constructing efficient algorithms for solving two types of matching problems. We use this strategy to develop explicit algorithms for these two problems applied to strings (where the patterns are substrings) and arrays (where the patterns are subarrays or blocks). We also develop algorithms for these and related problems for trees, where the patterns are subtrees. Certain special cases of these algorithms are also discussed. Although we do not claim that these algorithms are optimal, we analyze each algorithm to estimate its computational cost. This provides some basis for choosing which algorithm is most desirable in any given situation.