More Time-Space Tradeoffs for Finding a Shortest Unique Substring

More Time-Space Tradeoffs for Finding a Shortest Unique Substring

We extend recent results regarding finding shortest unique substrings (SUSs) to obtain new time-space tradeoffs for this problem and the generalization of finding <i>k</i>-mismatch SUSs. Our new results include the first algorithm for finding a <i>k</i>-mismatch SUS in sublin...

Full description

Bibliographic Details
Main Authors: Hideo Bannai, Travis Gagie, Gary Hoppenworth, Simon J. Puglisi, Luís M. S. Russo
Format: Article
Language:English
Published: MDPI AG 2020-09-01
Series:Algorithms
Subjects:
shortest unique substring
k-mismatch SUS
time-space tradeoff
Karp–Rabin
sketching
suffix trees
Online Access:https://www.mdpi.com/1999-4893/13/9/234

Internet

https://www.mdpi.com/1999-4893/13/9/234

Similar Items