# More Time-Space Tradeoffs for Finding a Shortest Unique Substring
## 1 Introduction  
A shortest unique substring (SUS) of a given text \(T[1..n]\) is a substring containing a given position \(T[q]\) and occurring only once in \(T\), such that every shorter substring containing \(T[q]\) occurs at least twice in \(T\). For example, if \(T[1..11]=\text{ABRACADABRA}\) and \(q=3\), then \(T[3..5]=\text{RAC}\) is an SUS: it contains \(T[3]\), it occurs only once in \(T\), and each of the shorter substrings containing \(T[3]\)--i.e., \(T[3]=\text{R}\), \(T[2..3]=\text{BR}\) and \(T[3..4]=\text{RA}\)--occurs at least twice in \(T\). The problem of finding SUSs has attracted significant attention recently and many variants have been proposed--interval-SUSs, \(k\)-mismatch SUSs, palindromic-SUSs and range-SUSs--so what we refer to simply as SUS here are sometimes also called position-SUSs. In this paper, we are only interested in position-SUSs and \(k\)-mismatch SUSs, which we describe shortly. We refer readers to [PERSON] et al. 's very recent survey [1] for a more detailed discussion. Finding exact and approximate SUS has several applications in bioinformatics, including alignment-free genome comparison, PCR primer design, and the identification of DNA signatures distinguishing closely related organisms [2; 3; 4]. [PERSON], [PERSON], and [PERSON] [3] gave the definition of SUSs above, along with an \(O(n)\)-time and \(O(n)\)-space algorithm for finding an SUS for \(T[q]\) given \(q\)and an \(O(n^{2})\)-time, \(O(n)\)-space construction algorithm for an \(O(n)\)-space data structure that in \(O(1)\) time returns the endpoints of an SUS for \(T[q]\) given \(q\). [PERSON], [PERSON], and [PERSON] [5], [PERSON], [PERSON] and [PERSON] [6], and [PERSON], [PERSON], [PERSON], and [PERSON] [7] independently improved the construction time to \(O(n)\). [PERSON] and [PERSON] [8] reduced both the construction space and the space of the data structure to \(O\left(\frac{n\log\sigma}{\log n}\right)\) at the cost of increasing the construction time to \(O(n\log\sigma)\), where \(\sigma\) is the size of the alphabet, while keeping the query time constant. [PERSON] et al. [9] gave the following time-space tradeoffs for finding SUSs, assuming we have random access to \(T\) and \(\tau\) is a parameter:  
* given \(q\), we can find an SUS for \(T[q]\) in \(O(n\tau^{2}\log(n/\tau))\) time and \(O(n/\tau)\) space;
* in \(O(n\tau^{2}\log n)\) time and \(O(n/\tau)\) words plus \(4n+o(n)\) bits of space, we can build a \((4n+o(n))\)-bit data structure answering SUS queries in \(O(1)\) time; and,
* we can change the running time in both cases to \(O(n\tau\log^{c+1}n)\) at the cost of increasing the space by an additive \(O(n/\log^{c}n)\) and allowing for a low probability that the substrings are not shortest. Recently, [PERSON] [10] gave a simple low-memory randomized algorithm based on Karp-Rabin pattern matching, but did not give theoretical bounds for it. [PERSON], [PERSON], and [PERSON] [11] generalized the problem by defining a \(k\)-mismatch SUS to be a shortest substring containing \(T[q]\) that is not only unique, but also not within Hamming distance \(k\) of any other substring of \(T\). For example, if \(T[1..11]=\text{ABRACADABRA}\) and \(q=5\), then \(T[3..5]=\text{RAC}\) is a one-mismatch SUS, because no other substring is within Hamming distance 1 of it and each of the shorter substrings containing \(T[5]\)--i.e., \(T[5]=\text{C}\), \(T[4..5]=\text{AC}\) and \(T[5..6]=\text{CA}\)--is within edit distance of some other substring. On the other hand, \(T[4..6]=\text{ACA}\) is not a 1-mismatch SUS, although it also has length 3, because the Hamming distance between ACA and ADA is 1. [PERSON] et al. gave an \(O(n^{2})\)-time, \(O(n)\)-space construction of an \(O(n)\)-space data structure, which, given \(q\), in \(O(1)\) time returns the endpoints of a \(k\)-mismatch SUS for \(T[q]\). [PERSON], [PERSON], and [PERSON] [12] reduced the construction time to \(O(n\log^{k}n)\) at the cost of increasing the construction space to \(O(kn)\), and [PERSON] and [PERSON] [13] gave a GPU algorithm that is fast in practice.