Rapid identification of repeated patterns in strings, trees and arrays

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.

REFERENCES

• 1: Morris, James H. and Vaughan Pratt, ";A Linear Pattern Matching Algorithm"; Report #40, Computing Center, University of California at Berkeley, 1970.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Pattern matching

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Trees

General Terms:
Theory