Skip to Main content Skip to Navigation
Conference papers

Factor oracle : a new structure for pattern matching

Abstract : 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.
Document type :
Conference papers
Complete list of metadatas

Cited literature [15 references]  Display  Hide  Download

https://hal-upec-upem.archives-ouvertes.fr/hal-00619846
Contributor : Maxime Crochemore <>
Submitted on : Wednesday, February 13, 2013 - 6:17:58 PM
Last modification on : Wednesday, February 26, 2020 - 7:06:05 PM
Long-term archiving on: : Tuesday, May 14, 2013 - 3:59:36 AM

File

9911-sofsem.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

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⟩

Share

Metrics

Record views

339

Files downloads

742