QR Code

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 sublinear space, which we obta...

Full description

Saved in:
Main Authors: Hideo Bannai, Travis Gagie, Gary Hoppenworth, Simon J. Puglisi, Luís M. S. Russo
Format: Artigo
Language:Inglês
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
Tags: Add Tag
No Tags, Be the first to tag this record!

Similar Items