1972 · 276 citations · 1 references
ComputingComputer ScienceAlgorithmsCombinatoricsData StructuresPattern RecognitionSearching AlgorithmsString AlgorithmsComplexity Of String AlgorithmsMatching AlgorithmsPattern MatchingPattern Matching AlgorithmsString SearchString SearchingTree Pattern Matching
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.
1
Linear pattern matching algorithms
Peter Weiner · 1973 · 1.8K citations