Name
Abstract | ||
|---|---|---|
A substring Q of a string S is called a shortest unique substring (SUS) for position p in S, if Q occurs exactly once in S, this occurrence of Q contains position p, and every substring of S which contains position p 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 position p all the SUSs for position p can be answered quickly. There exist optimal O(n)-time preprocessing scheme which answers queries in optimal O(k) time, where n is the length of S and k is the number of SUSs for a query position. In this paper, we reveal structural, combinatorial properties underlying this problem: Namely, we show that the number of intervals in S that correspond to SUSs for all positions in S is less than 1.5n. We also show that this is a matching upper and lower bound. |
Year | Venue | DocType |
|---|---|---|
2017 | CPM | Conference |
Volume | Citations | PageRank |
abs/1609.07220 | 1 | 0.35 |
References | Authors | |
6 | 4 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Takuya Mieno | 1 | 4 | 3.48 |
| Shunsuke Inenaga | 2 | 595 | 79.02 |
| Hideo Bannai | 3 | 620 | 79.87 |
| Masayuki Takeda | 4 | 902 | 79.24 |