Factor oracle : a new structure for pattern matching - Archive ouverte HAL Accéder directement au contenu
Communication Dans Un Congrès Année : 1999

Factor oracle : a new structure for pattern matching

Résumé

We introduce a new automaton on a word p, sequence of letters taken in an alphabet Σ, that we call factor oracle. This automaton is acyclic, recognizes at least the factors of p, has m+1 states and a linear number of transitions. We give an on-line construction to build it. We use this new structure in string matching algorithms that we conjecture optimal according to the experimental results. These algorithms are as effecient as the ones that already exist using less memory and being more easy to implement.
Fichier principal
Vignette du fichier
9911-sofsem.pdf (314.96 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-00619846 , version 1 (13-02-2013)

Identifiants

Citer

Cyril Allauzen, Maxime Crochemore, Mathieu Raffinot. Factor oracle : a new structure for pattern matching. 26th Seminar on Current Trends in Theory and Practice of Informatics (SOFSEM'99), Nov 1999, Milovy, Czech Republic, Czech Republic. pp.291-306, ⟨10.1007/3-540-47849-3_18⟩. ⟨hal-00619846⟩
228 Consultations
695 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More