Truly Alphabet-Independent Two-Dimensional Pattern Matching

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. >

Authors

• Zvi Galil
• Kunsoo Park

Keywords

• Pattern matching
• Text processing
• Testing
• Computer science
• Birds
• Educational institutions
• Alphabet
• End Stage
• Search String
• Linear Time
• Vector Form
• Upper Left Corner
• Occurrence Patterns
• King’s College London
• Positive Part
• Power-of-two
• Consistency Checks
• Lattice Points
• Vector Lines
• Point In The Text
• Quadrant I
• Dimensional Patterns