An alphabet independent approach to two-dimensional pattern matching. (English) Zbl 0804.68056

Amir, Amihood; Benson, Gary; Farach, Martin

SIAM J. Comput. 23, No. 2, 313-323 (1994).

Summary: There are many solutions to the string matching problem that are strictly linear in the input size and independent of alphabet size. Furthermore, the model of computation for these algorithms is very weak: they allow only simple arithmetic and comparisons of equality between characters of the input. In contrast, algorithms for two-dimensional matching have needed stronger models of computation, most notably assuming a totally ordered alphabet. The fastest algorithms for two-dimensional matching have therefore had a logarithmic dependence on the alphabet size. In the worst case, this gives an algorithm that runs in \(O(n^ 2\log m)\) with \(O(m^ 2\log m)\) preprocessing.
The authors show an algorithm for two-dimensional matching with an \(O(n^ 2)\) text-scanning phase. Furthermore, the text scan requires no special assumptions about the alphabet, i.e., it runs on the same model as the standard linear-time string-matching algorithm. The pattern preprocessing requires an ordered alphabet and runs with the same alphabet dependency as the previously known algorithms.

MSC:

68W10	Parallel algorithms in computer science
68Q05	Models of computation (Turing machines, etc.) (MSC2010)
68Q25	Analysis of algorithms and problem complexity

Keywords:

pattern matching; multidimensional matching; period; string matching