Truly alphabet-independent two-dimensional pattern matching
- 1 January 1992
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 247-256
- https://doi.org/10.1109/sfcs.1992.267767
Abstract
A. Amir, G. Benson and M. Farach (see Proc. 24th STOC, p.59-68 (1992)) gave an algorithm for two-dimensional pattern matching (ABF for short) whose text processing is independent of the alphabet and takes O(n/sup 2/) time, but whose pattern processing is dependent on the alphabet and takes O(m/sup 2/log mod Sigma mod ) time. The authors present an algorithm that is truly independent of the alphabet and takes linear O(m/sup 2/+n/sup 2/) time. As in the Knuth-Morris-Pratt algorithm, the only operation on the alphabet is the equality test of two symbols. All previous algorithms except the ABF algorithm reduce the two-dimensional problem into one-dimensional string matching, and use known techniques in string matching. The ABF algorithm uses two-dimensional periodicity for text processing, but their pattern processing resorts to one-dimensional techniques. The authors present a two-dimensional technique for both pattern processing and text processing.<>Keywords
This publication has 11 references indexed in Scilit:
- Efficient pattern matching with scalingJournal of Algorithms, 1992
- Alphabet independent two dimensional matchingPublished by Association for Computing Machinery (ACM) ,1992
- An Optimal $O(\log\log n)$ Time Parallel String Matching AlgorithmSIAM Journal on Computing, 1990
- A technique for two-dimensional pattern matchingCommunications of the ACM, 1989
- Efficient randomized pattern-matching algorithmsIBM Journal of Research and Development, 1987
- Optimal parallel pattern matching in stringsInformation and Control, 1985
- An O(n log n) algorithm for finding all repetitions in a stringJournal of Algorithms, 1984
- A Technique for Extending Rapid Exact-Match String Matching to Arrays of More than One DimensionSIAM Journal on Computing, 1978
- Two dimensional pattern matchingInformation Processing Letters, 1977
- Fast Pattern Matching in StringsSIAM Journal on Computing, 1977