2026-07-20T05:47:02Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:6503 2024-03-06T10:38:23Z ddc:004 open_access

Shortest Unique Substring Queries on Run-Length Encoded Strings Mieno, Takuya Inenaga, Shunsuke Bannai, Hideo Takeda, Masayuki string algorithms shortest unique substring run-length encoding We consider the problem of answering shortest unique substring (SUS) queries on run-length encoded strings. For a string S, a unique substring u = S[i..j] is said to be a shortest unique substring (SUS) of S containing an interval [s, t] (i <= s <= t <= j) if for any i' <= s <= t <= j' with j-i > j'-i', S[i'..j'] occurs at least twice in S. Given a run-length encoding of size m of a string of length N, we show that we can construct a data structure of size O(m+pi_s(N, m)) in O(m log m + pi_c(N, m)) time such that queries can be answered in O(pi_q(N, m) + k) time, where k is the size of the output (the number of SUSs), and pi_s(N,m), pi_c(N,m), pi_q(N,m) are, respectively, the size, construction time, and query time for a predecessor/successor query data structure of m elements for the universe of [1,N]. Using the data structure by Beam and Fich (JCSS 2002), this results in a data structure of O(m) space that is constructed in O(m log m) time, and answers queries in O(sqrt(log m/loglog m)+k) time. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Takuya Mieno and Shunsuke Inenaga and Hideo Bannai and Masayuki Takeda 2016 Is Part Of LIPIcs, Volume 58, 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2016.69 urn:nbn:de:0030-drops-65033 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2016.69 eng https://creativecommons.org/licenses/by/3.0/legalcode