There are many solutions to the string matching problem that are stric
tly linear in the input size and independent of alphabet size. Further
more, the model of computation for these algorithms is very weak: they
allow only simple arithmetic and comparisons of equality between char
acters of the input. In contrast, algorithms for two-dimensional match
ing 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(n2 log
m) with O(m2 log m) preprocessing. The authors show an algorithm for
two-dimensional matching with an O(n2) text-scanning phase. Furthermor
e, the text scan requires no special assumptions about the alphabet, i
.e., it runs on the same model as the standard linear-time string-matc
hing algorithm. The pattern preprocessing requires an ordered alphabet
and runs with the same alphabet dependency as the previously known al
gorithms.