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...

Whakaahuatanga katoa

I tiakina i:
Ngā kaituhi matua: Hideo Bannai, Travis Gagie, Gary Hoppenworth, Simon J. Puglisi, Luís M. S. Russo
Hōputu: Artigo
Reo:Inglês
I whakaputaina: MDPI AG 2020-09-01
Rangatū:Algorithms
Ngā marau:
shortest unique substring
k-mismatch SUS
time-space tradeoff
Karp–Rabin
sketching
suffix trees
Urunga tuihono:https://www.mdpi.com/1999-4893/13/9/234
Ngā Tūtohu: Tāpirihia he Tūtohu
Kāore He Tūtohu, Me noho koe te mea tuatahi ki te tūtohu i tēnei pūkete!

Ngā tūemi rite