TY - GEN
T1 - Compact Data Structures for Shortest Unique Substring Queries
AU - Mieno, Takuya
AU - Köppl, Dominik
AU - Nakashima, Yuto
AU - Inenaga, Shunsuke
AU - Bannai, Hideo
AU - Takeda, Masayuki
N1 - Publisher Copyright:
© 2019, Springer Nature Switzerland AG.
PY - 2019
Y1 - 2019
N2 - Given a string T of length n, a substring of T is called a shortest unique substring (SUS) for an interval [s, t] if (a) u occurs exactly once in T, (b) u contains the interval [s, t] (i.e.), and (c) every substring v of T with containing [s, t] occurs at least twice in T. Given a query interval, the interval SUS problem is to output all the SUSs for the interval [s, t]. In this article, we propose a bits data structure answering an interval SUS query in output-sensitive time, where is the number of returned SUSs. Additionally, we focus on the point SUS problem, which is the interval SUS problem for. Here, we propose a bits data structure answering a point SUS query in the same output-sensitive time.
AB - Given a string T of length n, a substring of T is called a shortest unique substring (SUS) for an interval [s, t] if (a) u occurs exactly once in T, (b) u contains the interval [s, t] (i.e.), and (c) every substring v of T with containing [s, t] occurs at least twice in T. Given a query interval, the interval SUS problem is to output all the SUSs for the interval [s, t]. In this article, we propose a bits data structure answering an interval SUS query in output-sensitive time, where is the number of returned SUSs. Additionally, we focus on the point SUS problem, which is the interval SUS problem for. Here, we propose a bits data structure answering a point SUS query in the same output-sensitive time.
UR - http://www.scopus.com/inward/record.url?scp=85075648001&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85075648001&partnerID=8YFLogxK
U2 - 10.1007/978-3-030-32686-9_8
DO - 10.1007/978-3-030-32686-9_8
M3 - Conference contribution
AN - SCOPUS:85075648001
SN - 9783030326852
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 107
EP - 123
BT - String Processing and Information Retrieval - 26th International Symposium, SPIRE 2019, Proceedings
A2 - Brisaboa, Nieves R.
A2 - Puglisi, Simon J.
PB - Springer
T2 - 26th International Symposium on String Processing and Information Retrieval, SPIRE 2019
Y2 - 7 October 2019 through 9 October 2019
ER -