More Time-Space Tradeoffs for Finding a Shortest Unique Substring

Show full item record



Bannai , H , Gagie , T , Hoppenworth , G , Puglisi , S J & Russo , L M S 2020 , ' More Time-Space Tradeoffs for Finding a Shortest Unique Substring ' , Algorithms , vol. 13 , no. 9 , 234 .

Title: More Time-Space Tradeoffs for Finding a Shortest Unique Substring
Author: Bannai, Hideo; Gagie, Travis; Hoppenworth, Gary; Puglisi, Simon J.; Russo, Luis M. S.
Contributor: University of Helsinki, Department of Computer Science
Date: 2020-09-18
Language: eng
Number of pages: 9
Belongs to series: Algorithms
ISSN: 1999-4893
Abstract: 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) log L) time using random access to T, or in O(n(L/m) log(2) (L) log log sigma) time using O((L/m) log(2) L) sequential passes over T. We then describe how, for constant k, with high probability, we can find a k-mismatch SUS in O(n(1+epsilon) L/m) time using O(n(epsilon)L/m) sequential passes over T, again using only m words of workspace. Finally, we also describe a deterministic algorithm that takes O (n tau log sigma log n) time to find an SUS using O(n/tau) words of workspace, where tau is a parameter.
Subject: shortest unique substring
k-mismatch SUS
time-space tradeoff
suffix trees
113 Computer and information sciences

Files in this item

Total number of downloads: Loading...

Files Size Format View
algorithms_13_00234.pdf 252.2Kb PDF View/Open

This item appears in the following Collection(s)

Show full item record