# A Survey on Shortest Unique Substring Queries
## 2 Preliminaries  
### Definitions  
Let \(\mathcal{S}[1,n]\) be a string of length \(n\) (i.e., \(|\mathcal{S}|=n\)) over an alphabet set \(\Sigma\) and \(\mathcal{S}[i]\) is the ith character of \(\mathcal{S}\). The substring of \(\mathcal{S}\) which starts at position \(i\) and ends at position \(j\) of \(\mathcal{S}\) is denoted by \(\mathcal{S}[i,j]\). We have \(1\leq i\leq j\leq n\). If \(j<i\), then \(\mathcal{S}[i,j]\) is an empty string. A prefix of \(\mathcal{S}\) is a substring \(\mathcal{S}[1,i]\) of \(\mathcal{S}\) for some \(1\leq i\leq n\). \(\mathcal{S}[1,i]\) is a proper prefix if \(i\
eq n\). A suffix of \(\mathcal{S}\) is a substring \([j,n]\) for some \(1\leq j\leq n\). It is a proper suffix if \(j\
eq 1\). We say \(\mathcal{S}[i,j]\) covers position \(p\), if \(i\leq p\leq j\). \(\mathcal{S}[i^{\prime},j^{\prime}]\) is a proper substring of \(\mathcal{S}[i,j]\) if \(i\leq i^{\prime}\leq j^{\prime}\leq j\) and \(|\mathcal{S}[i,j]|>|\mathcal{S}[i^{\prime},j^{\prime}]|\). A substring \(\mathcal{S}[i,j]\) is a unique substring if there is no other substring \(\mathcal{S}[i^{\prime},j^{\prime}]\) such that \(\mathcal{S}[i,j]=\mathcal{S}[i^{\prime},j^{\prime}]\), where \(=\) indicates the identicality of two strings. The shortest unique substring (\(\mathsf{SUS}\)) covering position \(p\) is a unique substring of \(\mathcal{S}\) that contains \(\mathcal{S}[p]\), and there is no other unique substring with shorter length containing \(\mathcal{S}[p]\). Note that there might exist more than one \(\mathsf{SUS}\) covering position \(p\). \(\mathcal{S}[i,j]\) is a _minimal unique substring_ (\(\mathsf{MUS}\)) if it is a unique substring and there is no proper substring of \(\mathcal{S}[i,j]\) that is also unique. \(\mathcal{S}[p,j]\) is called the _left-bounded_ SUS for position \(p\), \(\mathsf{LSUS}(p)\), if \(\mathcal{S}[p,j]\) is unique and there is no other substring \(\mathcal{S}[p,j^{\prime}]\) which is also unique for \(p\leq j^{\prime}<j\). Symmetrically, \(\mathcal{S}[j,p]\) is _right-bounded_ SUS for position \(p\), \(\mathsf{RSUS}(p)\), if it is a unique substring and there is no other unique substring \(\mathcal{S}[j^{\prime},p]\), where \(j<j^{\prime}\leq p\).  
\(H(\mathcal{S}_{1},\mathcal{S}_{2})\) denotes the _Hamming distance_ between two strings \(\mathcal{S}_{1}\) and \(\mathcal{S}_{2}\) of equal length, defined as the number of string positions where characters differ. \(\mathcal{S}[i,j]\) is a _k-mismatch unique substring_ if there is no substring \(\mathcal{S}[i^{\prime},j^{\prime}]\) such that \(i^{\prime}\
eq i,j-i=j^{\prime}-i^{\prime}\) and \(H(\mathcal{S}[i,j],\mathcal{S}[i^{\prime},j^{\prime}])\leq k\). The _k-_mismatch left-bounded shortest unique substring \(\mathsf{LSUS}\) starting at position \(p\), denoted as \(\mathsf{LSUS}_{p}\), is a _k-_mismatch unique substring \(\mathcal{S}[p,j]\), such that either \(p=j\) or any proper prefix of \(\mathcal{S}[p,j]\) is not _k-_mismatch unique. _k-_mismatch RSUS and _k-_mismatch MUS can be defined similarly.  
The longest common prefix of two suffixes \(\mathcal{S}[p,n]\) and \(\mathcal{S}[q,n]\) denoted by \(\mathsf{LCP}(\mathcal{S}[p,n],\mathcal{S}[q,n])\), is the longest common prefix between \(\mathcal{S}[p,n]\) and \(\mathcal{S}[q,n]\). The _k-_mismatch longest common prefix of \(\mathcal{S}[p,n]\) and \(\mathcal{S}[q,n]\) denoted as \(\mathsf{LCP}^{k}(\mathcal{S}[p,n],\mathcal{S}[q,n])\) is the longest prefix which has Hamming distance \(\leq\)k between two suffixes.