Name
Abstract | ||
|---|---|---|
A substring u of a string T is called a minimal unique substring (MUS) of T if u occurs exactly once in T and any proper substring of u occurs at least twice in T. In this paper, we study the problem of computing MUSs for a sliding window over a given string T. We first show how the set of MUSs can change when the window slides over T. We then present an
$$O(n\log \sigma ')$$
-time and O(d)-space algorithm to compute MUSs for a sliding window of size d over the input string T of length n, where
$$\sigma '\le d$$
is the maximum number of distinct characters in every window. |
Year | DOI | Venue |
|---|---|---|
2022 | 10.1007/s00453-021-00864-1 | Algorithmica |
Keywords | DocType | Volume |
Minimal unique substring, Sliding window, Suffix tree | Journal | 84 |
Issue | ISSN | Citations |
3 | 0178-4617 | 0 |
PageRank | References | Authors |
0.34 | 13 | 6 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Takuya Mieno | 1 | 0 | 1.01 |
| Yuta Fujishige | 2 | 5 | 2.47 |
| Yuto Nakashima | 3 | 0 | 1.35 |
| Shunsuke Inenaga | 4 | 595 | 79.02 |
| Hideo Bannai | 5 | 620 | 79.87 |
| Masayuki Takeda | 6 | 9 | 13.78 |