# A Survey on Shortest Unique Substring Queries
## 5 Approximate-SUS Queries
### [PERSON] et al.'s Framework
### [PERSON] et al. 's Framework  
[PERSON], [PERSON], and [PERSON] considered solving Problem 4 in the place of \(S\), \(A\), and \(B\), where \(S\) is for storing string \(\mathcal{S}\), \(A\) and \(B\) are two empty arrays for storing the starting and ending positions of the rightmost \(k\)-mismatch SUS of each position. They prove the \(k\)-mismatch version of Lemma 2. Here, we explain the high level of their in-place framework for solving both Problems 1 and 4 which has three stages. Let \(\mathsf{LSUS}_{p}^{k}\) be the \(k\)-mismatch left bounded shortest unique substring starting at position \(p\). In the first stage, they compute \(\mathsf{LSUS}_{i}^{k}\) for all \(i\), in place of \(A\) and \(B\). At the end of this step, each \(B[i]\) stores the ending position of \(\mathsf{LSUS}_{i}^{k}\). This procedure takes linear time when \(k=0\) and \(\mathcal{O}(n^{2})\) time for \(k\geq 1\) because of their dynamic programming approach. Let \(\mathsf{SLS}_{p}^{k}\) be the shortest k-mismatch \(\mathsf{LSUS}\) covering position \(p\). In the second stage, they use array \(B\), computed from the previous stage, to find the rightmost \(\mathsf{SLS}_{i}^{k}\) for all \(i\) in place of \(A\) and \(B\). Each \(A[i]\) stores the largest \(j\) such that \(\mathsf{LSUS}_{j}^{k}\) is an \(\mathsf{SLS}_{j}^{k}\). Thus, if \(\mathsf{SLS}_{i}^{k}\) exists, it is equal to \(\mathcal{S}[A[i]\cdots B[i]]\). This takes \(\mathcal{O}(n)\) time for all \(k\geq 0\). At the last stage, they use both \(A\) and \(B\) to compute \(\mathsf{SUS}_{i}^{k}\) for all \(i\), in the place of \(A\) and \(B\). At the end of the stage, \(A[i]\) and \(B[i]\) store the starting and ending positions of the rightmost \(\mathsf{SUS}_{i}^{k}\). This step also takes linear time for any \(k\geq 0\). Note that only one stage requires the quadratic time. They implemented their algorithm in C using \(libdivusfort\) library for the suffix array construction. Their contribution can be summarized as follows:  
**Theorem 8**. : _Using an additional \(2n\) words each of size \(\lceil\log_{2}(n)\rceil\) bits, and \(n\) bytes of space for storing the input string, [PERSON] et al. [3] provided a theoretically in-place framework to solve both exact and the approximate position SUS using a total of \(\mathcal{O}(n)\) and \(\mathcal{O}(n^{2})\) time, respectively._  
### [PERSON] et al. 's Framework  
In order to reduce the quadratic time complexity for solving \(k\)-mismatch SUS queries, [PERSON] et al. [9] presented an average time complexity of \(\mathcal{O}(n\log^{k}n)\) using \(\mathcal{O}(kn)\) space. They follow the technique provided by [PERSON] et al. [39] for solving \(k\)-mismatch average common substring. Let the \(k\)-mismatch left-bounded longest repeat starting at position \(i\) denoted by \(\mathsf{LLR}_{i}^{k}\) be a \(k\)-mismatch repeat substring \(\mathcal{S}[i,j]\) such that either \(j=n\) or \(\mathcal{S}[i,j+1]\) is a \(k\)-mismatch unique. Consider \(L\) as an array of length \(n\) where \(L[i]=\big{|}\mathsf{LLR}_{i}^{k}\big{|}\). Now, the algorithm discussed in Section 5.2 can be applied to compute \(\mathsf{SUS}_{i}^{k}\) for each position \(i\) in \(\mathcal{S}\) in linear time and space. Computing array \(L\) can be a substitution for stage one of the [PERSON] et al. 's work [3]. To avoid \(\mathcal{O}(n^{2})\) time, instead of comparing every pair of suffixes of \(\mathcal{S}\), they presented an expected \(\mathcal{O}(m\log^{k}m)\) time for calculating each entry of \(L\) using the technique in [39], where \(m\) is the total length of two suffixes used in computing \(L[i]\) as follows:  
\[L[i]=\max\{|\mathsf{LCP}^{k}(\mathcal{S}_{i},\mathcal{S}_{j})|j\
eq i\}\]  
The total time complexity to compute every entry of \(L\) would be expected \(\mathcal{O}(n\log^{k}n)\). In 2020, [PERSON] et al. [10] published a new version of their work which provides algorithmic bounds for \(k\)-mismatch SUS problem. They presented an algorithm which can solve Problem 4 using \(\mathcal{O}(n\log^{k}n)\) time and \(\mathcal{O}(n)\) space.