TY - GEN

T1 - Minimal Unique Substrings and Minimal Absent Words in a Sliding Window

AU - Mieno, Takuya

AU - Kuhara, Yuki

AU - Akagi, Tooru

AU - Fujishige, Yuta

AU - Nakashima, Yuto

AU - Inenaga, Shunsuke

AU - Bannai, Hideo

AU - Takeda, Masayuki

N1 - Publisher Copyright:
© 2020, Springer Nature Switzerland AG.

PY - 2020

Y1 - 2020

N2 - A substring u of a string T is called a minimal unique substring (MUS) of T if u occurs exactly once in T and any proper substring of u occurs at least twice in T. A string w is called a minimal absent word (MAW) of T if w does not occur in T and any proper substring of w occurs in T. In this paper, we study the problems of computing MUSs and MAWs in a sliding window over a given string T. We first show how the set of MUSs can change in a sliding window over T, and present an-time and O(d)-space algorithm to compute MUSs in a sliding window of width d over T, where is the maximum number of distinct characters in every window. We then give tight upper and lower bounds on the maximum number of changes in the set of MAWs in a sliding window over T. Our bounds improve on the previous results in Crochemore et al. (2017).

AB - A substring u of a string T is called a minimal unique substring (MUS) of T if u occurs exactly once in T and any proper substring of u occurs at least twice in T. A string w is called a minimal absent word (MAW) of T if w does not occur in T and any proper substring of w occurs in T. In this paper, we study the problems of computing MUSs and MAWs in a sliding window over a given string T. We first show how the set of MUSs can change in a sliding window over T, and present an-time and O(d)-space algorithm to compute MUSs in a sliding window of width d over T, where is the maximum number of distinct characters in every window. We then give tight upper and lower bounds on the maximum number of changes in the set of MAWs in a sliding window over T. Our bounds improve on the previous results in Crochemore et al. (2017).

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

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

U2 - 10.1007/978-3-030-38919-2_13

DO - 10.1007/978-3-030-38919-2_13

M3 - Conference contribution

AN - SCOPUS:85079091632

SN - 9783030389185

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 148

EP - 160

BT - SOFSEM 2020

A2 - Chatzigeorgiou, Alexander

A2 - Dondi, Riccardo

A2 - Herodotou, Herodotos

A2 - Kapoutsis, Christos

A2 - Manolopoulos, Yannis

A2 - Papadopoulos, George A.

A2 - Sikora, Florian

PB - Springer

T2 - 46th International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2020

Y2 - 20 January 2020 through 24 January 2020

ER -