Combinatorics of minimal absent words for a sliding window
2022
A string is called a minimal absent word (MAW) for another string if does not occur in but the proper substrings of occur in . For example, let be the alphabet. Then, the set of MAWs for string is . 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 is shifted over the input string of length , where . We present upper and lower bounds on the maximum number of changes in the set of MAWs for a sliding window over , both in the cases of general alphabets and binary alphabets. Our bounds improve on the previously known best bounds [Crochemore et al., 2020].
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
0
References
0
Citations
NaN
KQI