Absent words in a sliding window with applications

Maxime Crochemore (1, 2) , Alice Héliou (3) , Gregory Kucherov (2, 4) , Laurent Mouchard (5) , Solon Pissis (6) , Yann Ramusat (7)

1 Department of Informatics [King's College London]
2 LIGM - Laboratoire d'Informatique Gaspard-Monge
3 AMIBIO - Algorithms and Models for Integrative BIOlogy
4 Skoltech - Skolkovo Institute of Science and Technology [Moscow]
5 QuantIF-LITIS - Equipe Quantification en Imagerie Fonctionnelle
6 CWI - Centrum voor Wiskunde en Informatica
7 VALDA - Value from Data

An absent word of a word y is a word that does not occur in y. It is then called minimal if all its proper factors occur in y. In fact, minimal absent words (MAWs) provide useful information about y and thus have several applications. In this paper, we propose an algorithm that maintains the set of MAWs of a fixed-length window sliding over y online. Our algorithm represents MAWs through nodes of the suffix tree. Specifically, the suffix tree of the sliding window is maintained using modified Senft's algorithm (Senft, 2005), itself generalizing Ukkonen's online algorithm (Ukkonen, 1995). We then apply this algorithm to the approximate pattern-matching problem under the Length Weighted Index distance (Chairungsee and Crochemore, 2012). This results in an online -time algorithm for finding approximate occurrences of a word x in y, , where σ is the alphabet size.

Mots clés: Online algorithms; Algorithms on strings; Pattern matching; Absent words; Forbidden words

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

Maxime Crochemore, Alice Héliou, Gregory Kucherov, Laurent Mouchard, Solon Pissis, et al.. Absent words in a sliding window with applications. Information and Computation, 2019, pp.104461. ⟨10.1016/j.ic.2019.104461⟩. ⟨hal-02414839⟩