Constant-space string matching in sublinear average time

Maxime Crochemore 1 Leszek Gąsieniec 2 Wojciech Rytter 3, 4
1 LIGM - Laboratoire d'Informatique Gaspard-Monge
2 MPII - Max-Planck-Institut für Informatik
3 Institute of Computer Science
4 Department of Computer Science [Liverpool]
Abstract : Given two strings: pattern P of length m and text T of length n. The string-matching problem is to find all occurrences of the pattern P in the text T. We present a simple string-matching algorithm which works in average o(n) time with constant additional space for one-dimensional texts and two-dimensional arrays. This is the first attempt to the small-space string-matching problem in which sublinear time algorithms are delivered. More precisely we show that all occurrences of one- or two-dimensional patterns can be found in O(n/r) average time with constant memory, where r is the repetition size (size of the longest repeated subword) of P
Document type :
Conference papers
Complete list of metadatas

Cited literature [12 references]  Display  Hide  Download
https://hal-upec-upem.archives-ouvertes.fr/hal-00619976
Contributor : Maxime Crochemore <>
Submitted on : Tuesday, March 26, 2013 - 10:37:39 PM
Last modification on : Thursday, September 20, 2018 - 7:54:02 AM
Long-term archiving on: Thursday, June 27, 2013 - 2:30:12 AM

File

seq97.pdf
Files produced by the author(s)

Identifiers

Collections

CNRS | UNIV-MLV | LIGM_ALGO | LIGM | ENPC | PARISTECH | UPEC-UPEM

Citation

Maxime Crochemore, Leszek Gąsieniec, Wojciech Rytter. Constant-space string matching in sublinear average time. Compression and Complexity of Sequences (Positano, 1997), Jun 1997, Salerno, Italy. pp.230-239, ⟨10.1109/SEQUEN.1997.666918⟩. ⟨hal-00619976⟩

Export

BibTeX TEI DC DCterms EndNote

Share

Metrics

Record views

266

Files downloads

208

Contact

Informations

CCSD