 |
HAL UPEC - UPEM Portal |  |
 |
Conference papers
On the suffix automaton with mismatches
Abstract : In this paper we focus on the construction of the minimal deterministic finite automaton S_k that recognizes the set of suffixes of a word w up to k errors. We present an algorithm that makes use of S_k in order to accept in an efficient way the language of all suffixes of w up to k errors in every window of size r, where r is the value of the repetition index of w. Moreover, we give some experimental results on some well-known words, like prefixes of Fibonacci and Thue-Morse words, and we make a conjecture on the size of the suffix automaton with mismatches.
Cited literature [22 references]
https://hal-upec-upem.archives-ouvertes.fr/hal-00620159
Contributor : Maxime Crochemore Connect in order to contact the contributor
Submitted on : Monday, October 3, 2016 - 6:48:34 PM
Last modification on : Saturday, January 15, 2022 - 3:57:36 AM
Long-term archiving on: : Friday, February 3, 2017 - 3:14:43 PM
Contributor : Maxime Crochemore Connect in order to contact the contributor
Submitted on : Monday, October 3, 2016 - 6:48:34 PM
Last modification on : Saturday, January 15, 2022 - 3:57:36 AM
Long-term archiving on: : Friday, February 3, 2017 - 3:14:43 PM
File
07-CEGM-ciaa.pdf
Files produced by the author(s)