| Autor: |
Hideo Bannai, Travis Gagie, Gary Hoppenworth, Simon J. Puglisi, Luís M. S. Russo |
| Jazyk: |
angličtina |
| Rok vydání: |
2020 |
| Předmět: |
|
| Zdroj: |
Algorithms, Vol 13, Iss 9, p 234 (2020) |
| Druh dokumentu: |
article |
| ISSN: |
1999-4893 |
| DOI: |
10.3390/a13090234 |
| Popis: |
We extend recent results regarding finding shortest unique substrings (SUSs) to obtain new time-space tradeoffs for this problem and the generalization of finding k-mismatch SUSs. Our new results include the first algorithm for finding a k-mismatch SUS in sublinear space, which we obtain by extending an algorithm by Senanayaka (2019) and combining it with a result on sketching by Gawrychowski and Starikovskaya (2019). We first describe how, given a text T of length n and m words of workspace, with high probability we can find an SUS of length L in O(n(L/m)logL) time using random access to T, or in O(n(L/m)log2(L)loglogσ) time using O((L/m)log2L) sequential passes over T. We then describe how, for constant k, with high probability, we can find a k-mismatch SUS in O(n1+ϵL/m) time using O(nϵL/m) sequential passes over T, again using only m words of workspace. Finally, we also describe a deterministic algorithm that takes O(nτlogσlogn) time to find an SUS using O(n/τ) words of workspace, where τ is a parameter. |
| Databáze: |
Directory of Open Access Journals |
| Externí odkaz: |
|
|
Nepřihlášeným uživatelům se plný text nezobrazuje |
K zobrazení výsledku je třeba se přihlásit.
|
