Two-dimensional Prefix String Matching and Covering on Square Matrices

Two linear algorithms are presented. One for computing the longest prefix of a square pattern that occurs in every position of a given 2 dimensional array and one for computing all square covers of a given 2-dimensional array. Institut Gaspard Monge, Universite de Marne-la-Vallee, 2, rue de la Butte Verte, F-93160 Noisyle -Grand , France. Email: mac@litp.ibp.fr. y Department of Computer Science, King's College London, Strand, London, England and School of Computing, Curtin University, Perth, WA, Australia. Email: csi@dcs.kcl.ac.uk. Partially supported by SERC grants GR/F 00898 and GR/J 17844, NATO grant CRG 900293, ESPRIT BRA grant 7131 for ALCOM II, and MRC grant G 9115730. z Department of Computer Science, King's College London, Strand, London, U.K. Email: mo@dcs.kcl.ac.uk. Supported by a Medical Research Council Studenship. 1. Introduction In recent study of repetitive structures of strings, generalized notions of periods have been introduced. A typical regularity, the perio..