Name
Abstract | ||
|---|---|---|
Given a string T of length n, a substring u = T[i.. j] 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. i \leq s \leq t \leq j), and (c) every substring v of T with |v| < |u| containing [s, t] occurs at least twice in T. Given a query interval [s, t] \subset [1, n], the interval SUS problem is to output all the SUSs for the interval [s, t]. In this article, we propose a 4n + o(n) bits data structure answering an interval SUS query in output-sensitive O(occ) time, where occ is the number of returned SUSs. Additionally, we focus on the point SUS problem, which is the interval SUS problem for s = t. Here, we propose a \lceil (log2 3 + 1)n \rceil + o(n) bits data structure answering a point SUS query in the same output-sensitive time. |
Year | DOI | Venue |
|---|---|---|
2019 | 10.1007/978-3-030-32686-9_8 | SPIRE |
Field | DocType | Volume |
Data structure,Discrete mathematics,Combinatorics,Substring,Mathematics | Journal | abs/1905.12854 |
Citations | PageRank | References |
0 | 0.34 | 0 |
Authors | ||
6 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Takuya Mieno | 1 | 0 | 1.35 |
| Dominik Köppl | 2 | 0 | 0.34 |
| Yuto Nakashima | 3 | 57 | 19.52 |
| Shunsuke Inenaga | 4 | 595 | 79.02 |
| Hideo Bannai | 5 | 620 | 79.87 |
| Masayuki Takeda | 6 | 9 | 13.78 |