# More Time-Space Tradeoffs for Finding a Shortest Unique Substring
## 4 A Deterministic Algorithm
### Putting the Occurrences Together  
We now determine which substrings in the batch \(B\) are not unique in \(T\). Notice that, for any \(1\leq i_{1}<i_{2}<i_{3}\leq k\), occurrences of \(B_{i_{1}}\) and \(B_{i_{3}}\) which share the same occurrence of \(y\) implies an occurrence of \(B_{i_{2}}\) also sharing the occurrence of \(y\). Therefore, we maintain an integer arrays \(R\) of size \(k+1\), where all elements are initially \(0\), in order to record the start and end of ranges in \(B\) that have been found to occur in \(T\). We use the DAWG \(D(x\$)\), the Crochemore-Perrin algorithm for \(y\), and the Suffix Tree \(S(z\$)\), and maintain three parallel scans on \(T\), shifted so that the three parts are detected in sync. More precisely, at position \(i\), we maintain the following:  
1. the longest suffix \(x^{*}\) of \(T[i-\ell-k+2..i-\ell]\) that is also a suffix of \(x\) using the modified DAWG \(D(x\$)\),
2. whether \(y=T[i-\ell+1..i-k+1]\) using the Crochemore-Perrin algorithm, and
3. the longest prefix \(z^{*}\) of \(T[i-k+2..i]\) that is also a prefix of \(z\) while using the modified suffix tree \(S(z\$)\). If \(|x^{*}|+|y|+|z^{*}|<\ell\), then no substrings in \(B\) occur here. On the other hand, if \(|x^{*}|+|y|+|z^{*}|\geq\ell\), then certainly one or more substrings in \(B\) occur here. Specifically, if \(|x^{*}|+|y|+|z^{*}|\geq\ell\), then substrings \(B_{k-|x^{*}|}\) through \(B_{k+|y|+|z^{*}|-\ell}\) in \(B\) occur here. We increment \(R[k-|x^{*}|]\) and decrement \(R[k+|y|+|z^{*}|-\ell+1]\). After the scan, we process \(R\) and compute for \(i=1,\ldots,k\), \(R^{\prime}[i]=\sum_{j=1}^{i}R[j]\), i.e., \(R^{\prime}[1]=R[1]\) and \(R^{\prime}[i]=R^{\prime}[i-1]+R[i]\), which represents the total number of occurrences of \(B_{i}\) in \(T\) (including those which contain \(q\)). Thus, the total is \(\mathcal{O}(n\log\sigma)\) time. At any moment \(\mathcal{O}(m)\) space is used. We have shown that we can determine the uniqueness of all the substrings in a batch \(B\) in \(T\) in \(\mathcal{O}(n\log\sigma)\) time and \(\mathcal{O}(m)\) space. Because there are \(\lceil\frac{\ell}{m}\rceil\) batches of possible substrings of length \(\ell\) covering \(p\), we can determine the uniqueness of all substrings in all batches in \(\mathcal{O}((\frac{\ell}{m}+1)n\log\sigma)\) time and using at most \(\mathcal{O}(m)\) words at any moment. Theorem 4.2: _There is a deterministic algorithm that computes the shortest unique substring (SUS) of a text \(T[1..n]\) that covers some query position \(p\) chosen at runtime in \(\mathcal{O}(n/\tau)\) words of workspace and \(\mathcal{O}(n\tau\log\sigma\log n)\) time._  
Proof of Theorem 4.2: If there is a unique substring in \(T\) with length \(\ell\) and \(\ell<n\), then there is a unique substring in \(T\) with length greater than \(\ell\). This property lets us use exponential search over the length \(\ell\) of the shortest unique substring (SUS), with Lemma 1 as a sub-algorithm, in order to find the SUS that covers a query position \(p\) in \(\mathcal{O}(m)\) words and \(\mathcal{O}((\frac{L}{m}+1)n\log\sigma\log L)\) time, where \(L\) is the length of the SUS. Setting \(m=n/\tau\), this yields a time complexity of \(\mathcal{O}((L\tau+n)\log\sigma\log L)\subseteq\mathcal{O}(n\tau\log\sigma\log n )\subset o(n\tau^{2}\log\sigma\log(n/\tau))\). Algorithm 2 shows the pseudo-code. ```
1 for next choice of \(\ell\) in binary search for \(L\in[1,n]\)
2 % If there exists a unique substring of length \(\ell\) that contains position \(q\), then \(L\leq\ell\).