On the suffix automaton with mismatches

Maxime Crochemore (1) , Chiara Epifanio (2) , Alessandra Gabriele (2) , Filippo Mignosi (3)

1 LIGM - Laboratoire d'Informatique Gaspard-Monge
2 Dipartimento di Matematica e Applicazioni [Palermo]
3 DI - Dipartimento di Informatica [Italy]

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.

Mots clés: combinatorics on words; suffix automata; languages with mismatches; approximate string matching

Domaines: Algorithme et structure de données [cs.DS]

Maxime Crochemore, Chiara Epifanio, Alessandra Gabriele, Filippo Mignosi. On the suffix automaton with mismatches. 12th International Conference on Implementation and Application of Automata (CIAA'07), 2007, Prague, Czech Republic. pp.144-156, ⟨10.1007/978-3-540-76336-9_15⟩. ⟨hal-00620159⟩