Combinatorics of minimal absent words for a sliding window
Tooru Akagi, Yuki Kuhara, Takuya Mieno, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda · Theoretical Computer Science · 2022
A string w is called a minimal absent word (MAW) for another string T if w does not occur in T but the proper substrings of w occur in T. For example, let Σ={a,b,c} be the alphabet. Then, the set of MAWs for string w=abaab is {aaa,aaba,bab,bb,c}. In this paper, we study combinatorial properties of MAWs in the sliding window model, namely, how the set of MAWs changes when a sliding window of fixed length d is shifted over the input string T of length n, where 1≤d