Minimal Unique Substrings and Minimal Absent Words in a Sliding Window

Takuya Mieno; Yuki Kuhara; Tooru Akagi; Yuta Fujishige; Yuto Nakashima; Shunsuke Inenaga; Hideo Bannai; Masayuki Takeda

doi:10.1007/978-3-030-38919-2_13

Minimal Unique Substrings and Minimal Absent Words in a Sliding Window

Takuya Mieno, Yuki Kuhara, Tooru Akagi, Yuta Fujishige, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda

Mathematical Informatics

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

7 Citations (Scopus)

Abstract

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).

Original language	English
Title of host publication	SOFSEM 2020
Subtitle of host publication	Theory and Practice of Computer Science - 46th International Conference on Current Trends in Theory and Practice of Informatics, SOFSEM 2020, Proceedings
Editors	Alexander Chatzigeorgiou, Riccardo Dondi, Herodotos Herodotou, Christos Kapoutsis, Yannis Manolopoulos, George A. Papadopoulos, Florian Sikora
Publisher	Springer
Pages	148-160
Number of pages	13
ISBN (Print)	9783030389185
DOIs	https://doi.org/10.1007/978-3-030-38919-2_13
Publication status	Published - 2020
Event	46th International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2020 - Limassol, Cyprus Duration: Jan 20 2020 → Jan 24 2020

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	12011 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	46th International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2020
Country/Territory	Cyprus
City	Limassol
Period	1/20/20 → 1/24/20

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Computer Science(all)

Access to Document

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

Cite this

Mieno, T., Kuhara, Y., Akagi, T., Fujishige, Y., Nakashima, Y., Inenaga, S., Bannai, H., & Takeda, M. (2020). Minimal Unique Substrings and Minimal Absent Words in a Sliding Window. In A. Chatzigeorgiou, R. Dondi, H. Herodotou, C. Kapoutsis, Y. Manolopoulos, G. A. Papadopoulos, & F. Sikora (Eds.), SOFSEM 2020: Theory and Practice of Computer Science - 46th International Conference on Current Trends in Theory and Practice of Informatics, SOFSEM 2020, Proceedings (pp. 148-160). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 12011 LNCS). Springer. https://doi.org/10.1007/978-3-030-38919-2_13

Minimal Unique Substrings and Minimal Absent Words in a Sliding Window. / Mieno, Takuya; Kuhara, Yuki; Akagi, Tooru et al.
SOFSEM 2020: Theory and Practice of Computer Science - 46th International Conference on Current Trends in Theory and Practice of Informatics, SOFSEM 2020, Proceedings. ed. / Alexander Chatzigeorgiou; Riccardo Dondi; Herodotos Herodotou; Christos Kapoutsis; Yannis Manolopoulos; George A. Papadopoulos; Florian Sikora. Springer, 2020. p. 148-160 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 12011 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Mieno, T, Kuhara, Y, Akagi, T, Fujishige, Y, Nakashima, Y , Inenaga, S, Bannai, H & Takeda, M 2020, Minimal Unique Substrings and Minimal Absent Words in a Sliding Window. in A Chatzigeorgiou, R Dondi, H Herodotou, C Kapoutsis, Y Manolopoulos, GA Papadopoulos & F Sikora (eds), SOFSEM 2020: Theory and Practice of Computer Science - 46th International Conference on Current Trends in Theory and Practice of Informatics, SOFSEM 2020, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 12011 LNCS, Springer, pp. 148-160, 46th International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2020, Limassol, Cyprus, 1/20/20. https://doi.org/10.1007/978-3-030-38919-2_13

Mieno T, Kuhara Y, Akagi T, Fujishige Y, Nakashima Y , Inenaga S et al. Minimal Unique Substrings and Minimal Absent Words in a Sliding Window. In Chatzigeorgiou A, Dondi R, Herodotou H, Kapoutsis C, Manolopoulos Y, Papadopoulos GA, Sikora F, editors, SOFSEM 2020: Theory and Practice of Computer Science - 46th International Conference on Current Trends in Theory and Practice of Informatics, SOFSEM 2020, Proceedings. Springer. 2020. p. 148-160. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-030-38919-2_13

Mieno, Takuya ; Kuhara, Yuki ; Akagi, Tooru et al. / Minimal Unique Substrings and Minimal Absent Words in a Sliding Window. SOFSEM 2020: Theory and Practice of Computer Science - 46th International Conference on Current Trends in Theory and Practice of Informatics, SOFSEM 2020, Proceedings. editor / Alexander Chatzigeorgiou ; Riccardo Dondi ; Herodotos Herodotou ; Christos Kapoutsis ; Yannis Manolopoulos ; George A. Papadopoulos ; Florian Sikora. Springer, 2020. pp. 148-160 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{adf150dfb5a540698cbc037c1f7f15c9,

title = "Minimal Unique Substrings and Minimal Absent Words in a Sliding Window",

abstract = "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).",

author = "Takuya Mieno and Yuki Kuhara and Tooru Akagi and Yuta Fujishige and Yuto Nakashima and Shunsuke Inenaga and Hideo Bannai and Masayuki Takeda",

note = "Publisher Copyright: {\textcopyright} 2020, Springer Nature Switzerland AG.; 46th International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2020 ; Conference date: 20-01-2020 Through 24-01-2020",

year = "2020",

doi = "10.1007/978-3-030-38919-2_13",

language = "English",

isbn = "9783030389185",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer",

pages = "148--160",

editor = "Alexander Chatzigeorgiou and Riccardo Dondi and Herodotos Herodotou and Christos Kapoutsis and Yannis Manolopoulos and Papadopoulos, {George A.} and Florian Sikora",

booktitle = "SOFSEM 2020",

}

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

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 -

Minimal Unique Substrings and Minimal Absent Words in a Sliding Window

Abstract

Publication series

Conference

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this