Back to Search
Start Over
Combinatorics of minimal absent words for a sliding window.
- Source :
-
Theoretical Computer Science . Aug2022, Vol. 927, p109-119. 11p. - Publication Year :
- 2022
-
Abstract
- 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 < n. We present tight upper and lower bounds on the maximum number of changes in the set of MAWs for a sliding window over T , both in the cases of general alphabets and binary alphabets. Our bounds improve on the previously known best bounds [Crochemore et al., 2020]. [ABSTRACT FROM AUTHOR]
- Subjects :
- *COMBINATORICS
*VOCABULARY
Subjects
Details
- Language :
- English
- ISSN :
- 03043975
- Volume :
- 927
- Database :
- Academic Search Index
- Journal :
- Theoretical Computer Science
- Publication Type :
- Academic Journal
- Accession number :
- 158389022
- Full Text :
- https://doi.org/10.1016/j.tcs.2022.06.002