2026-07-24T10:09:16Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:7346 2024-03-06T10:40:08Z ddc:004 open_access

Tight Bounds on the Maximum Number of Shortest Unique Substrings Mieno, Takuya Inenaga, Shunsuke Bannai, Hideo Takeda, Masayuki shortest unique substrings maximal unique substrings A substring Q of a string S is called a shortest unique substring (SUS) for interval [s,t] in S, if Q occurs exactly once in S, this occurrence of Q contains interval [s,t], and every substring of S which contains interval [s,t] and is shorter than Q occurs at least twice in S. The SUS problem is, given a string S, to preprocess S so that for any subsequent query interval [s,t] all the SUSs for interval [s,t] can be answered quickly. When s = t, we call the SUSs for [s, t] as point SUSs, and when s <= t, we call the SUSs for [s, t] as interval SUSs. There exist optimal O(n)-time preprocessing scheme which answers queries in optimal O(k) time for both point and interval SUSs, where n is the length of S and k is the number of outputs for a given query. In this paper, we reveal structural, combinatorial properties underlying the SUS problem: Namely, we show that the number of intervals in S that correspond to point SUSs for all query positions in S is less than 1.5n, and show that this is a matching upper and lower bound. Also, we consider the maximum number of intervals in S that correspond to interval SUSs for all query intervals in S. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Takuya Mieno and Shunsuke Inenaga and Hideo Bannai and Masayuki Takeda 2017 Is Part Of LIPIcs, Volume 78, 28th Annual Symposium on Combinatorial Pattern Matching (CPM 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CPM.2017.24 urn:nbn:de:0030-drops-73460 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2017.24 eng https://creativecommons.org/licenses/by/3.0/legalcode