Two-dimensional prefix string matching and covering on square matrices

Maxime Crochemore (1) , Costas S. Iliopoulos (2) , Maureen Korda (2)

1 LIGM - Laboratoire d'Informatique Gaspard-Monge
2 DCS - Department of Computer Science

Two linear time algorithms are presented. One for determining, for every position in a given square matrix, the longest prefix of a given pattern (also a square matrix) that occurs at that position and one for computing all square covers of a given two-dimensional square matrix.

Domaines: Algorithme et structure de données [cs.DS]

Maxime Crochemore, Costas S. Iliopoulos, Maureen Korda. Two-dimensional prefix string matching and covering on square matrices. Algorithmica, 1998, 20 (1), pp.353-373. ⟨10.1007/PL00009200⟩. ⟨hal-00619570⟩