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 metadata

Cited literature [15 references]  Display  Hide  Download
Contributor : Maxime Crochemore Connect in order to contact the contributor
Submitted on : Wednesday, February 13, 2013 - 6:17:58 PM
Last modification on : Saturday, January 15, 2022 - 3:58:16 AM
Long-term archiving on: : Tuesday, May 14, 2013 - 3:59:36 AM


Files produced by the author(s)



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⟩



Record views


Files downloads