 |
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 <>
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
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)