TY - JOUR

T1 - Absent words in a sliding window with applications

AU - Crochemore, Maxime

AU - Héliou, Alice

AU - Kucherov, Gregory

AU - Mouchard, Laurent

AU - Pissis, Solon P.

AU - Ramusat, Yann

PY - 2020/2

Y1 - 2020/2

N2 - 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 O(σ|y|)-time algorithm for finding approximate occurrences of a word x in y, |x|≤|y|, where σ is the alphabet size.

AB - 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 O(σ|y|)-time algorithm for finding approximate occurrences of a word x in y, |x|≤|y|, where σ is the alphabet size.

KW - Absent words

KW - Algorithms on strings

KW - Forbidden words

KW - Online algorithms

KW - Pattern matching

UR - http://www.scopus.com/inward/record.url?scp=85071718815&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85071718815&partnerID=8YFLogxK

U2 - 10.1016/j.ic.2019.104461

DO - 10.1016/j.ic.2019.104461

M3 - Article

AN - SCOPUS:85071718815

VL - 270

JO - Information and Computation

JF - Information and Computation

SN - 0890-5401

M1 - 104461

ER -