Constant-space string matching in sublinear average time - Archive ouverte HAL Accéder directement au contenu
Communication Dans Un Congrès Année : 1997

Constant-space string matching in sublinear average time

Résumé

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
Fichier principal
Vignette du fichier
seq97.pdf (238.07 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-00619976 , version 1 (26-03-2013)

Identifiants

Citer

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⟩
127 Consultations
190 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More