# More Time-Space Tradeoffs for Finding a Shortest Unique Substring
## 2 Tradeoffs with Karp-Rabin Pattern Matching  
If we know an SUS for \(T[q]\) has length at most \(L\), then we can search in \(T\) for repetitions of the substrings of \(T[q-L+1..q+L-1]\) in \(T\), using \(O(L)\) words of workspace and \(O(n)\) time. To do this, we build a suffix tree [18; 19; 20] for \(T[q-L+1..q+L-1]\) and scan \(T\), always descending in the suffix tree as much as possible and then following a suffix link. Suppose that, at some point, we have just read \(T[i]\) and we are at string depth \(d\) in the suffix tree. If \(T[i-d+1..i]\) is not completely contained in \(T[q-L+1..q+L-1]\) and \(d\) is the largest string depth we have reached along the edge we are currently descending, then we mark with \(d\) the node below that edge. After we have scanned \(T\), we can extract from the marked suffix tree the shortest string, such that:  
* its locus is a leaf (meaning it occurs only once in \(T[q-L+1..q+L-1]\)),
* that leaf's label is at most \(q\) and its label plus the string's length is at least \(q\) (so an occurrence of the string contains \(T[q]\)), and
* that leaf is not marked with a number greater than or equal to the strings length (meaning we have not seen a copy of the string elsewhere in \(T\)). If we do not know \(L\), then we can find it via exponential search, still using \(O(L)\) words of workspace, but \(O(n\log L)\) time and \(O(\log L)\) sequential passes over \(T\). Since finding an SUS is relatively easy if we can use workspace proportional to its length, even if that length is unknown, in this paper we assume that we have less workspace. Obviously, we can find an SUS containing \(T[q]\) while using \(O(1)\) words of workspace if we are willing to spend \(O(L^{3}n)\) time, where \(L\) is the length of that SUS. For example, we can use the simple Algorithm 1. This algorithm can easily be improved to take \(O(L^{2}n\log L)\) time by replacing the linear search for \(L\) with an exponential search. It can then be further improved to take \(O(Ln\log L)\) time with high probability, while still using \(O(1)\) words of workspace, by replacing naive pattern matching with Karp-Rabin pattern matching. The resulting randomized algorithm can be either Monte Carlo if we do not verify matches or Las Vegas if we do, and the probability of failure can be made inversely proportional to any fixed polynomial of \(n\) without changing the asymptotic bounds. \begin{table}
\begin{tabular}{c c c c c} \hline \hline
**Source** & **Time** & **Space (Words)** & **Deterministic** & **Data Structure** \\ \hline [PERSON] et al. [3] & \(O(n)\) & \(O(n)\) & yes & no \\  & \(O(n^{2})\) & \(O(n)\) & yes & yes \\ [PERSON] et al. [5] & \(O(n)\) & \(O(n)\) & yes & yes \\ [PERSON] et al. [6] & \(O(n)\) & \(O(n)\) & yes & yes \\ [PERSON] et al. [7] & \(O(n)\) & \(O(n)\) & yes & yes \\ [PERSON] and [PERSON] [8] & \((\alpha\log\sigma)\) & \(O(n\log(\sigma)/\log n)\) & yes & yes \\ [PERSON] et al. [9] & \(O(n\tau^{2}\log(n/\tau))\) & \(O(n/\tau)\) & yes & no \\  & \(O(n\tau\log^{c+1}n)\) & \(O(n/\tau+n/\log^{c}n)\) & no & no \\  & \(O(n\tau^{2}\log n)\) & \(4n+o(n)\) bits & yes & yes \\  & \(O(n\tau\log^{c+1}n)\) & \(4n+o(n)\) bits & no & yes \\ Theorem 1 & \(O(n(L/m)\log L)\) & \(m\) & no & no \\ Theorem 4 & \(O(n\tau\log\sigma\log n)\) & \(O(n/\tau)\) & yes & no \\ [PERSON] et al. [11] & \(O(n^{2})\) & \(O(n)\) & yes & yes \\ [PERSON] et al. [12] & \(O(n\log^{k}n)\) & \(O(kn)\) & yes & yes \\ Theorem 3 & \(O(n^{1+e}L/m)\) & \(m\) & no & no \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Previous bounds and our results for finding SUSs (the first twelve results) and \(k\)-mismatch SUSs (the last three), where \(n\) is the length of the text, \(\sigma\) is the alphabet size, \(L\) is the length of the SUS or \(k\)-mismatch SUS, and \(m,\tau<n\) and \(c\) are parameters. Theorem 3 is Monte Carlo and we require \(m=\omega(n^{e})\), so that the probability of failure can be made inversely proportional to any fixed polynomial of \(n\).