Name
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]. |
Year | DOI | Venue |
|---|---|---|
2022 | 10.1016/j.tcs.2022.06.002 | Theoretical Computer Science |
Keywords | DocType | Volume |
Combinatorics on words,Minimal absent words,Sliding window | Journal | 927 |
ISSN | Citations | PageRank |
0304-3975 | 0 | 0.34 |
References | Authors | |
4 | 7 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Tooru Akagi | 1 | 0 | 0.34 |
| Yuki Kuhara | 2 | 0 | 0.34 |
| Takuya Mieno | 3 | 0 | 1.01 |
| Yuto Nakashima | 4 | 0 | 1.35 |
| Shunsuke Inenaga | 5 | 595 | 79.02 |
| Hideo Bannai | 6 | 620 | 79.87 |
| Masayuki Takeda | 7 | 9 | 13.78 |