Resumen
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)" role="presentation">??(??(??/??)log??)O(n(L/m)logL)
O
(
n
(
L
/
m
)
log
L
)
time using random access to T, or in O(n(L/m)log2(L)loglogσ)" role="presentation">??(??(??/??)log2(??)loglog??)O(n(L/m)log2(L)loglogs)
O
(
n
(
L
/
m
)
log
2
(
L
)
log
log
s
)
time using O((L/m)log2L)" role="presentation">??((??/??)log2??)O((L/m)log2L)
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(n1+ϵL/m)" role="presentation">??(??1+????/??)O(n1+?L/m)
O
(
n
1
+
?
L
/
m
)
time using O(nϵL/m)" role="presentation">??(??????/??)O(n?L/m)
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)" role="presentation">??(????log??log??)O(ntlogslogn)
O
(
n
t
log
s
log
n
)
time to find an SUS using O(n/τ)" role="presentation">??(??/??)O(n/t)
O
(
n
/
t
)
words of workspace, where τ" role="presentation">??t
t
is a parameter.