 |
HAL UPEC - UPEM Portal |  |
 |
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.
Cited literature [15 references]
https://hal-upec-upem.archives-ouvertes.fr/hal-00619846
Contributor : Maxime Crochemore Connect in order to contact the contributor
Submitted on : Wednesday, February 13, 2013 - 6:17:58 PM
Last modification on : Tuesday, October 19, 2021 - 11:25:53 AM
Long-term archiving on: : Tuesday, May 14, 2013 - 3:59:36 AM
Contributor : Maxime Crochemore Connect in order to contact the contributor
Submitted on : Wednesday, February 13, 2013 - 6:17:58 PM
Last modification on : Tuesday, October 19, 2021 - 11:25:53 AM
Long-term archiving on: : Tuesday, May 14, 2013 - 3:59:36 AM
File
9911-sofsem.pdf
Files produced by the author(s)