Compressed Consecutive Pattern Matching - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Pré-Publication, Document De Travail Année : 2023

Compressed Consecutive Pattern Matching

Résumé

Originating from the work of Navarro and Thankanchan [TCS 2016], the problem of consecutive pattern matching is a variant of the fundamental pattern matching problem, where one is given a text and a pair of patterns $p_1,p_2$, and must compute consecutive occurrences of $p_1,p_2$ in the text. Assuming that the text is given as a straight-line program of size $g$, we develop an algorithm that computes all consecutive occurrences of $p_{1}, p_{2}$ in optimal $O(g+|p_1|+|p_2|+output)$ time. As a corollary, we also derive an algorithm that reports all co-occurrences separated by a distance $d \in [a,b]$ in $O(g+|p_1|+|p_2|+\occ)$ time and an algorithm that reports the top-$k$ closest co-occurrences in $O(g+|p_1|+|p_2|+k)$ time.
Fichier principal
Vignette du fichier
main.pdf (263.22 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-04251959 , version 1 (20-10-2023)

Licence

Paternité

Identifiants

  • HAL Id : hal-04251959 , version 1

Citer

Paweł Gawrychowski, Garance Gourdel, Tatiana Starikovskaya, Teresa Anna Steiner. Compressed Consecutive Pattern Matching. 2023. ⟨hal-04251959⟩
64 Consultations
58 Téléchargements

Partager

Gmail Facebook X LinkedIn More