Alphabet-independent two-dimensional witness computation

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