Alphabet-Independent Two-Dimensional Witness Computation
Zvi Galil, Kunsoo Park · SIAM Journal on Computing · 1996
We study two-dimensional periodicity, introduced by Amir and Benson. We characterize periods of a two-dimensional array, namely, the vectors such that two copies of the array, one shifted by the vector over the other, overlap without a mismatch. Using this characterization, we design an alphabet-independent linear-time algorithm for two-dimensional witness computation, i.e., an $O(m^2 )$-time algorithm that finds periods of an $m \times m$ array as well as witnesses against nonperiods of the array among the vectors whose length is less than ${m / 4}$. The constant in the O notation does not depend on the alphabet size. Combined with the alphabet-independent text-processing algorithm of Amir, Benson, and Farach [SIAM J. Comput., 23 (1994), pp. 313–323], this leads to the first alphabet-independent linear-time algorithm for two-dimensional pattern matching.