@inproceedings{f99b4d646ee44d92880d4698b5b7c0d2,
title = "Optimal two-dimensional compressed matching",
abstract = "Recent proliferation of digitized data and the expected unprecedented growth in the volume of stored and transmitted data motivated the definition of the compressed matching paradigm. This is the problem of efficiently finding a pattern P in a compressed text T without the need to decompress. We present the first optimal two-dimensional compressed matching algorithm. The compression under consideration is the two dimensional run-length compression, used by FAX transmission. We achieve optimal time by proving new properties of two-dimensional periodicity. This enables performing duels in which no witness is required. At the heart of the dueling idea lies the concept that two overlapping occurrences of a pattern in a text can use the content of a predetermined text position or witness in the overlap to eliminate one of them. Finding witnesses is a costly operation in a compressed text, thus the importance of witness-free dueling.",
author = "Amihood Amir and Gary Benson and Martin Farach",
note = "Publisher Copyright: {\textcopyright} 1994, Springer Verlag. All rights reserved.; Proceedings of the 1994 21st International Colloquium on Automata, Languages and Programming, ICALP'94 ; Conference date: 01-07-1994 Through 01-07-1994",
year = "1994",
doi = "10.1007/3-540-58201-0_70",
language = "English (US)",
isbn = "9783540582014",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "215--226",
editor = "Serge Abiteboul and Eli Shamir",
booktitle = "Automata, Languages and Programming - 21st International Colloquium, ICALP 1994, Proceedings",
}