More Time-Space Tradeoffs for Finding a Shortest Unique Substring

Abstract

We extend recent results regarding finding shortest unique substrings (SUSs) to obtain new time-space tradeoffs for this problem and the generalization of finding k-mismatch SUSs. Our new results include the first algorithm for finding a k-mismatch SUS in sublinear space, which we obtain by extending an algorithm by Senanayaka (2019) and combining it with a result on sketching by Gawrychowski and Starikovskaya (2019). We first describe how, given a text T of length n and m words of workspace, with high probability we can find an SUS of length L in $O\left(n\right(L/m)logL)$ time using random access to T, or in $O(n(L/m){log}^2\left(L\right)loglog\sigma )$ time using $O\left((L/m){log}^{2}L\right)$ sequential passes over T. We then describe how, for constant k, with high probability, we can find a k-mismatch SUS in $O(n^{1+ϵ}L/m)$ time using $O(n^{ϵ}L/m)$ sequential passes over T, again using only m words of workspace. Finally, we also describe a deterministic algorithm that takes $O(n\tau log\sigma logn)$ time to find an SUS using $O(n/\tau )$ words of workspace, where $\tau$ is a parameter.

1. Introduction

A shortest unique substring (SUS) of a given text $T[1..n]$ is a substring containing a given position $T\left[q\right]$ and occurring only once in T, such that every shorter substring containing $T\left[q\right]$ occurs at least twice in T. For example, if $T[1..11]=\mathrm{ABRACADABRA}$ and $q=3$, then $T[3..5]=\mathrm{RAC}$ is an SUS: it contains $T\left[3\right]$, it occurs only once in T, and each of the shorter substrings containing $T\left[3\right]$—i.e., $T\left[3\right]=\mathrm{R}$, $T[2..3]=\mathrm{BR}$ and $T[3..4]=\mathrm{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 Abedin 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]. Pei, Wu, and Yeh [3] gave the definition of SUSs above, along with an $O\left(n\right)$-time and $O\left(n\right)$-space algorithm for finding an SUS for $T\left[q\right]$ given q, and an $O\left(n^2\right)$-time, $O\left(n\right)$-space construction algorithm for an $O\left(n\right)$-space data structure that in $O\left(1\right)$ time returns the endpoints of an SUS for $T\left[q\right]$ given q. Hu, Pei, and Tao [5], İleri, Külekci and Xu [6], and Tsuruta, Inenaga, Bannai, and Takeda [7] independently improved the construction time to $O\left(n\right)$. Belazzougui and Cunial [8] reduced both the construction space and the space of the data structure to $O\left(\frac{nlog\sigma }{logn}\right)$ at the cost of increasing the construction time to $O(nlog\sigma )$, where $\sigma$ is the size of the alphabet, while keeping the query time constant. Ganguly 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\left[q\right]$ in $O(n{\tau }^{2}log(n/\tau ))$ time and $O(n/\tau )$ space;
• in $O(n{\tau }^{2}logn)$ time and $O(n/\tau )$ words plus $4n+o\left(n\right)$ bits of space, we can build a $(4n+o(n\left)\right)$-bit data structure answering SUS queries in $O\left(1\right)$ time; and,
• we can change the running time in both cases to $O\left(n\tau {log}^{c+1}n\right)$ 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, Senanayaka [10] gave a simple low-memory randomized algorithm based on Karp–Rabin pattern matching, but did not give theoretical bounds for it.

Hon, Thankachan, and Xu [11] generalized the problem by defining a k-mismatch SUS to be a shortest substring containing $T\left[q\right]$ that is not only unique, but also not within Hamming distance k of any other substring of T. For example, if $T[1..11]=\mathrm{ABRACADABRA}$ and $q=5$, then $T[3..5]=\mathrm{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\left[5\right]$—i.e., $T\left[5\right]=\mathrm{C}$, $T[4..5]=\mathrm{AC}$ and $T[5..6]=\mathrm{CA}$—is within edit distance of some other substring. On the other hand, $T[4..6]=\mathrm{ACA}$ is not a 1-mismatch SUS, although it also has length 3, because the Hamming distance between ACA and ADA is 1.

Hon et al. gave an $O\left(n^2\right)$-time, $O\left(n\right)$-space construction of an $O\left(n\right)$-space data structure, which, given q, in $O\left(1\right)$ time returns the endpoints of a k-mismatch SUS for $T\left[q\right]$. Allen, Thankachan, and Xu [12] reduced the construction time to $O\left(n{log}^{k}n\right)$ at the cost of increasing the construction space to $O\left(kn\right)$, and Schultz and Xu [13] gave a GPU algorithm that is fast in practice.

In Section 2, we show how Senanayaka’s approach can be extended, such that, given q and m words of workspace and random access to T, with high probability we can find an SUS containing $T\left[q\right]$ in $O\left(\right(L/m+1)nlogL)$ time. In Section 3, we show that, replacing Karp–Rabin pattern matching by a result on sketching by Golan and Porat [14], we can use $O\left((L/m+1){log}^{2}L\right)$ sequential passes over T instead of random access, at the cost of increasing the time to $O\left((L/m+1)n{log}^{2}L\right)$ and requiring $m=\omega (logL)$. Replacing Golan and Porat’s result by one by Gawrychowski and Starikovskaya [15], for constant k, we can find a k-mismatch SUS for $T\left[q\right]$ in $O(n^{1+ϵ}L/m)$ time using $O(n^{ϵ}L/m)$ sequential passes over T, now requiring $m=\omega \left(n^{ϵ}\right)$. Although the sketching results that we rely on are too sophisticated for us to explain them here, and to recent for us to be able to refer to one other than Golan and Porat’s and Gawrychowski and Starikovskaya’s papers themselves, we only use them only as black boxes, without relying on the details of how they work.

In Section 4, we describe a deterministic algorithm that makes use of directed acyclic word graphs (DAWGs) [16], the Crochemore-Perrin pattern matching algorithm [17], and suffix trees  [18,19,20], to compute an SUS in $O(n\tau log\sigma logn)$ time using $O(n/\tau )$ words of workspace, improving Ganguly et al.’s result when $\tau log(n/\tau )=\omega (log\sigma logn)$. Finally, in Section 5 we discuss some possible directions for future work.

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 \left(n^{ϵ}\right)$, so that the probability of failure can be made inversely proportional to any fixed polynomial of n. All of the data structures return an SUSs given q in $O\left(1\right)$ time and have the same final space as construction space, except that the construction-space bounds for Ganguly et al.’s third and fourth results are $O(n/\tau )$ words plus $4n+o\left(n\right)$ bits of space, and $O(n/\tau +n/{log}^{c}n)$ words plus $4n+o\left(n\right)$ bits.

Source	Time	Space (Words)	Deterministic	Data Structure
Pei et al. [3]	$O\left(n\right)$	$O\left(n\right)$	yes	no
	$O\left(n^2\right)$	$O\left(n\right)$	yes	yes
Hu et al. [5]	$O\left(n\right)$	$O\left(n\right)$	yes	yes
İleri et al. [6]	$O\left(n\right)$	$O\left(n\right)$	yes	yes
Tsuruta et al. [7]	$O\left(n\right)$	$O\left(n\right)$	yes	yes
Belazzougui and Cunial [8]	$O(nlog\sigma )$	$O(nlog(\sigma )/logn)$	yes	yes
Ganguly et al. [9]	$O(n{\tau }^{2}log(n/\tau ))$	$O(n/\tau )$	yes	no
	$O\left(n\tau {log}^{c+1}n\right)$	$O(n/\tau +n/{log}^{c}n)$	no	no
	$O(n{\tau }^{2}logn)$	$4n+o\left(n\right)$ bits	yes	yes
	$O\left(n\tau {log}^{c+1}n\right)$	$4n+o\left(n\right)$ bits	no	yes
Theorem 1	$O\left(n\right(L/m)logL)$	m	no	no
Theorem 4	$O(n\tau log\sigma logn)$	$O(n/\tau )$	yes	no
Hon et al. [11]	$O\left(n^2\right)$	$O\left(n\right)$	yes	yes
Allen et al. [12]	$O\left(n{log}^{k}n\right)$	$O\left(kn\right)$	yes	yes
Theorem 3	$O(n^{1+ϵ}L/m)$	m	no	no

summarizes known bounds for finding SUSs and k-mismatch SUSs, including those that we give in this paper.

2. Tradeoffs with Karp-Rabin Pattern Matching

If we know an SUS for $T\left[q\right]$ 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\left(L\right)$ words of workspace and $O\left(n\right)$ 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\left[i\right]$ 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\left[q\right]$), 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\left(L\right)$ words of workspace, but $O(nlogL)$ time and $O(logL)$ 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\left[q\right]$ while using $O\left(1\right)$ words of workspace if we are willing to spend $O\left(L^{3}n\right)$ 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}nlogL)$ time by replacing the linear search for L with an exponential search. It can then be further improved to take $O(LnlogL)$ time with high probability, while still using $O\left(1\right)$ words of workspace, by replacing naïve 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.

Algorithm 1 An $O\left(L^{3}n\right)$-time algorithm to find an shortest unique substring (SUS) of $T[1..n]$ containing $T\left[q\right]$, where L is the length of that SUS.

1 for ℓ from 1 to n    2 check each length ℓ in increasing order    3  for i from $q-\ell +1$ to q    4  % check all substrings of length ℓ that include $T\left[q\right]$    5   unmatchedflag ← true    6   % we have not yet seen a repetition of $T[i..i+\ell -1]$    7   for j from 1 to $n-\ell +1$    8    if $j\ne i$    9    % for $j\ne i$, compare $T[j..j+\ell -1]$ to $T[i..i+\ell -1]$    10     matchflag ← true    11     % we have not yet seen a mismatch between $T[j..j+\ell -1]$ and $T[i..i+\ell -1]$    12     for k from 0 to $\ell -1$    13      if $T[j+k]\ne T[i+k]$    14      % we have found a mismatch    15       matchflag ← false    16       break    17      end if    18     end for    19     if matchflag = true    20     % we have found a repetition of $T[i..i+\ell -1]$    21      unmatchedflag ← false    22      break    23     end if    24    end if    25   end for    26   if unmatchedflag = true    27   % there is no repetition of $T[i..i+\ell -1]$    28    print i, ℓ    29    return    30    % do not check longer substrings    31   end if    32  end for    33 end for

If we allow ourselves m words of workspace, then we can make the algorithm run in $O\left(\right(L/m+1)nlogL)$ time with high probability. To do this, when searching for repetitions of the ℓ substrings of length ℓ that contain $T\left[q\right]$, we process them in $\lceil \ell /m^{\prime }\rceil$ batches of size $m^{\prime }$, where $m^{\prime }=\Theta \left(m\right)$ depends on the ratio of the word-size to ${log}_{2}n$ and the power of n we want in the denominator in the probability of failure. We note that we compute the hashes of the substrings in the same batch by rolling them, in $O\left(L\right)$ total time, rather than computing each of them from scratch, which would take $O\left(L^2\right)$ total time.

Theorem 1.

With m words of workspace, with high probability we can find an SUS for $T\left[q\right]$ in $O\left(n\right(L/m)logL)$ time.

3. Tradeoffs with Sketching

For Karp–Rabin pattern matching, we must keep track of characters leaving a sliding window, for which we need either enough memory to store the contents of the sliding window—which, by assumption, we do not have—or random access to T. However, Golan and Porat [14] gave a Monte-Carlo randomized sketching algorithm that takes d patterns of maximum length ℓ, scans T one character at a time, and, for each position, reports the longest pattern with an occurrence ending at that position with probability of failure inversely proportional to any fixed polynomial in n. Their algorithm uses $O(loglog\sigma )$ time per character of T and $O(dlog\ell )$ space and does not use a sliding window, so it needs only sequential access to T. Replacing Karp–Rabin pattern matching with Golan and Porat’s result and searching for substrings of length ℓ in batches of size $\Theta (m/log\ell )$, so that we stay within our workspace bound m, we obtain the following result:

Theorem 2.

With $m=\omega (logL)$ words of workspace, with high probability we can find an SUS for $T\left[q\right]$ in $O(n(L/m){log}^2\left(L\right)loglog\sigma )$ time using $O\left((L/m){log}^{2}L\right)$ sequential passes over T.

Because Golan and Porat’s algorithm is Monte Carlo, so is our result; unlike Theorem 1, we cannot easily make it Las Vegas, since verifying matches requires random access. Again, our batch size depends on the ratio of the word-size to ${log}_{2}n$ and the power of n we want in the denominator in the probability of failure. The requirement that $m=\omega (logL)$ means the probability of failure can still be made inversely proportional to any fixed polynomial of n.

Gawrychowski and Starikovskaya [15] considered a harder version of the problem Golan and Porat studied, in which we are given a distance k and, for each position in T, we should report all of the patterns within Hamming distance k of substrings of T ending at that position. They gave a Monte-Carlo randomized sketching algorithm that searches for d patterns of length at most ℓ using $O(klo{g}^{k}d\mathrm{polylog}\left(\ell \right)+\mathrm{occ})$ time per character of T, where $\mathrm{occ}$ is the number of matches reported ending at that character, and $O\left(kd{log}^{k}d\mathrm{polylog}\left(\ell \right)\right)$ space. Replacing Golan and Porat’s algorithm with Gawrychowski and Starikovskaya’s and searching for substrings of length ℓ in batches of size $\Theta (m/n^{ϵ})$ for some positive constant $ϵ$, so that we stay within our workspace bound m for constant k, we obtain the following result:

Theorem 3.

For constant k and with $m=\omega \left(n^{ϵ}\right)$ words of workspace, with high probability we can find a k-mismatch SUS for $T\left[q\right]$ in $O(n^{1+ϵ}L/m)$ time using $O(n^{ϵ}L/m)$ sequential passes over T.

Like Theorem 2, this result is Monte Carlo and the probability of failure is inversely proportional to any fixed polynomial in n.

4. A Deterministic Algorithm

Lemma 1.

Given a length ℓ and a position p in a text $T[1..n]$ with alphabet size σ, there exists a deterministic algorithm that can determine whether there is a substring of length ℓ that covers position p and is unique in T in $\mathcal{O}((\frac{\ell }{m}+1)nlog\sigma )$ time and $\mathcal{O}\left(m\right)$ words of workspace.

Proof of Lemma 1.

There are at most ℓ possible substrings of length ℓ covering p that could be unique. We separate these substrings into $\lceil \frac{\ell }{m}\rceil$ batches of m substrings with adjacent starting positions. Note that there may be one remainder batch with less than m substrings.

Consider a batch B containing k substrings of length ℓ, where $1\le k\le m$. Let $B_i$ denote the substring in B with the $ith$ adjacent starting position in B. Subsequently, $B_1$ is the leftmost substring in B and $B_k$ is the rightmost substring in B.

Consider the following substrings:

$x=B_1[1..k-1]$

$z=B_k[\ell -k+2..\ell ]$

$y=B_1[k..\ell ]=B_k[1..\ell -k+1]$

It is useful to think of x as the prefix of $B_1$ that does not overlap with $B_k$ in T. Similarly, z is the suffix of $B_k$ that does not overlap with $B_1$. Finally, y is the suffix of $B_1$ and the prefix of $B_k$ that overlap with each other in T. Note that any substring in B is equal to $x_{suff}·y·z_{pref}$, where $x_{suff}$ is some suffix of x, $z_{pref}$ is some prefix of z and · denotes concatenation. For each batch, we will use the substrings x, y, and z to determine whether any of the k substrings in the batch occur in T.

We can scan T to enumerate all occurrences of suffixes of x, all occurrences of y, and all occurrences of prefixes of z. Using this information we can determine if any of the k substrings in the batch occur elsewhere in T and are therefore not unique. Suppose that we search text T and we find an occurrence of a suffix q of x, an occurrence r of y, and an occurrence of a prefix s of z. If $q=T[i..j]$, $r=T[j+1..j+1+\ell -k]$ and $s=T[j+2+\ell -k..\ell +i-1]$ for some i, $j\in [1,n],i\le j$, then we have found an occurrence of a substring in batch B in T. Specifically, if $qrs=B_a$ for some $B_a\in B$, then $B_a$ is not unique in T. □

4.1. Finding Occurrences of Suffixes of X

To enumerate all occurrences of suffixes of x in T, we construct the Directed Acyclic Word Graph (DAWG) [16] $D\left(x\$\right)$ with suffix links. $D\left(x\$\right)$ is the smallest deterministic automaton which accepts all suffixes of $x\$$ and it is known to have the following properties:

• Each edge is labeled by a single symbol, and the labels of all outgoing edges from a given node are distinct. The total number of nodes and edges is linear in the length of $x\$$.
• For any node u, let $P_u$ denote the set of strings that can be created by concatenating the labels of any path from the root to u. Subsequently, $P_u\subseteq \mathit{Substr}\left(x\$\right)$, and for any strings $p_1,p_2\in P_u$, the set of ending positions of occurrences of $p_1$ and $p_2$ in $x\$$ are equivalent, i.e.,

  $$\{j\mid p_1=\widehat{x}[j-|p_1|+1..j]\}=\{j\mid p_2=\widehat{x}[j-|p_2|+1..j]\}$$

  where $\widehat{x}=x\$$. This implies that $P_u=\{p_u[1..|p_u\left|\right],\dots ,p_u[k..|p_u\left|\right]\}$ for some $p_u$ (the longest element of $P_u$) and $1\le k\le |p_u|$.
• The suffix link $l\left(u\right)$ of a node u points to a node v such that the longest element of $P_v$ is $p_u^{\prime }[2..|p_u^{\prime }\left|\right]$, where $p_u^{\prime }$ is the shortest element of $P_u$.

For technical convenience, we can also consider an auxiliary node that the suffix link of the root points to, which has outgoing edges for all symbols to the root. $D\left(x\$\right)$ can be built in $\mathcal{O}(mlog\sigma )$ time and $\mathcal{O}\left(m\right)$ space [16]. Because the suffix links form a tree, we can also process the suffix link tree in linear time so that each node u holds a pointer $l^{\prime }\left(u\right)$ to the deepest ancestor v of u (possibly $v=u$) that has $ as an outgoing edge, i.e., the longest element $p_v$ of $P_v$ is the longest suffix of any $p\in P_u$ that is a suffix of x.

Using $D\left(x\$\right)$, we can incrementally compute for each $j=1,\dots ,n$, the position in the DAWG, which corresponds to the longest suffix $T[i..j]$ of $T[1..j]$ that is a substring of x in $O(nlog\sigma )$ overall time. Initially, $i=1$, and we start at the root of $D\left(x\$\right)$. For each character $T\left[j\right]$ for $j=1,\dots ,n$ and current node u, we traverse $D\left(x\$\right)$ by following the edge labelled $T\left[j\right]$ from u or if that edge does not exist, try again after following the suffix link to $l\left(u\right)$. When the suffix link is traversed, i is incremented, so that the length of $T[i..j-1]$ matches the length of the longest element in $P_{l\left(u\right)}$ ($-1$ for the auxiliary node, and 0 for the root node).

If, upon reading character $T\left[j^{*}\right]$, we arrive at a node u, then, $v=l^{\prime }\left(u\right)$ points to the (possibly empty) longest suffix $T[i^{*}..j^{*}]$ of $T[1..j^{*}]$ that is a suffix of x, so we have detected suffixes of x with lengths $0..j^{*}-i^{*}+1$ starting at positions $i\in [i^{*},j^{*}]$ and ending at position $j^{*}$ of T. In this manner, we can find occurrences of all suffixes of x in T in $\mathcal{O}(nlog\sigma )$ time.

4.2. Finding Occurrences of Y

To enumerate all the occurrences of y in T, we preprocess y in $\mathcal{O}(\ell -m)$ time and constant space using the Crochemore–Perrin preprocessing algorithm [17]. We can then find all occurrences of y in T in $\mathcal{O}\left(n\right)$ time and constant space.

4.3. Finding Occurrences of Prefixes of Z

To enumerate all occurrences of prefixes of z in T we construct the suffix tree [18,19,20] $S\left(z\$\right)$ with suffix links. Note that $S\left(z\$\right)$ contains exactly one node $z^{\prime }$, such that $path\left(z^{\prime }\right)=z\$$. For each explicit node in $S\left(z\$\right)$, we add a special pointer to the closest ancestor that is on the path from the root to $z^{\prime }$. This takes $\mathcal{O}(mlog\sigma )$ time and $\mathcal{O}\left(m\right)$ space. We start at the root of $S\left(z\$\right)$ and for $i=1,2,\cdots ,n$ we follow the edge labelled $T\left[i\right]$ until we reach a node u that has no outgoing edges labelled $T\left[i\right]$ available. We then use the special pointer at node u to find the closest ancestor v of u that is on the path to $z^{\prime }$. $path\left(v\right)$ then yields the longest prefix of z at position $i=1$ of T. Furthermore, every prefix of $path\left(v\right)$ is also a prefix of z, so we have detected prefixes of z with lengths $0..\left|path\right(v\left)\right|$ all starting at position i. To find the longest prefix of z at position $i+1$ of T, follow the suffix link of the node u we ended on for input $T\left[i\right]$ and repeat this process. In this manner, we can enumerate all the occurrences of all prefixes of z in T in $\mathcal{O}(nlog\sigma )$ time.

4.4. Putting the Occurrences Together

We now determine which substrings in the batch B are not unique in T. Notice that, for any $1\le i_1<i_2<i_3\le 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\left(x\$\right)$, the Crochemore–Perrin algorithm for y, and the Suffix Tree $S\left(z\$\right)$, 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:

• the longest suffix $x^{*}$ of $T[i-\ell -k+2..i-\ell ]$ that is also a suffix of x using the modified DAWG $D\left(x\$\right)$,
• whether $y=T[i-\ell +1..i-k+1]$ using the Crochemore–Perrin algorithm, and 
• the longest prefix $z^{*}$ of $T[i-k+2..i]$ that is also a prefix of z while using the modified suffix tree $S\left(z\$\right)$.

If $|x^{*}|+|y|+|z^{*}|<\ell$, then no substrings in B occur here. On the other hand, if $|x^{*}|+|y|+|z^{*}|\ge \ell$, then certainly one or more substrings in B occur here. Specifically, if $|x^{*}|+|y|+|z^{*}|\ge \ell$, then substrings $B_{k-|x^{*}|}$ through $B_{k+\left|y\right|+|z^{*}|-\ell }$ in B occur here. We increment $R[k-|x^{*}\left|\right]$ and decrement $R[k+|y|+|z^{*}|-\ell +1]$.

After the scan, we process R and compute for $i=1,\cdots ,k$, $R^{\prime }\left[i\right]={\sum }_{j=1}^{i}R\left[j\right]$, i.e., $R^{\prime }\left[1\right]=R\left[1\right]$ and $R^{\prime }\left[i\right]=R^{\prime }[i-1]+R\left[i\right]$, which represents the total number of occurrences of $B_i$ in T (including those which contain q). Thus, the total is $\mathcal{O}(nlog\sigma )$ time. At any moment $\mathcal{O}\left(m\right)$ 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}(nlog\sigma )$ time and $\mathcal{O}\left(m\right)$ space. Because there are $\lceil \frac{\ell }{m}\rceil$ batches of possible substrings of length ℓ covering p, we can determine the uniqueness of all substrings in all batches in $\mathcal{O}((\frac{\ell }{m}+1)nlog\sigma )$ time and using at most $\mathcal{O}\left(m\right)$ words at any moment. □

Theorem 4.

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 logn)$ time.

Proof of Theorem 4

If there is a unique substring in T with length ℓ and $\ell <n$, then there is a unique substring in T with length greater than ℓ. This property lets us use exponential search over the length ℓ 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}\left(m\right)$ words and $\mathcal{O}((\frac{L}{m}+1)nlog\sigma logL)$ 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 logL)\subseteq \mathcal{O}(n\tau log\sigma logn)\subset o(n{\tau }^{2}log\sigma log(n/\tau ))$. □

Algorithm 2 shows the pseudo-code.

Algorithm 2 An $O((\frac{L}{m}+1)nlog\sigma logL)\subseteq \mathcal{O}(n\tau log\sigma logn)$-time algorithm to find an SUS of $T[1..n]$ containing $T\left[q\right]$, where L is the length of the SUS.

1 for next choice of ℓ in binary search for $L\in [1,n]$    2 % If there exists a unique substring of length ℓ that contains position q, then $L\le \ell$.    3 % Otherwise, all of them are repeating so $L>\ell$    4  for i from $q-\ell +1$ to q step m    5  % check all substrings of length ℓ that include $T\left[q\right]$ in batches of size k (m except possibly last)    6   $k=min(m,q-i+1)$    7   $x=T[i..i+k-2]$, $y=T[i+k-1..i+\ell -1]$, $z=T[i+\ell ..i+\ell +k-2]$    8   Construct the DAWG $D\left(x\$\right)$    9   Preprocess y for the Crochemore-Perrin algorithm    10   Construct the suffix tree $S\left(z\$\right)$    11   for j from 1 to $k+1$    12    $R\left[j\right]=0$, $R^{\prime }\left[j\right]=0$    13   end for    14   for j from 1 to n    15    Compute longest common suffix $x^{*}$ of x and $T[j-\ell -k+2..j-\ell ]$ using $D\left(x\$\right)$    16    Compute whether $y=T[j-\ell +1..j-k+1]$, using Crochemore-Perrin algorithm    17    Compute longest common prefix $y^{*}$ of y and $T[j-k+2..j]$ using $S\left(z\$\right)$    18    if $|x^{*}|+|y|+|z|\ge \ell$ then    19     $R[k-|x^{*}\left|\right]=R[k-|x^{*}\left|\right]+1$    20     $R[k+|y|+|z^{*}|-\ell +1]=R[k+|y|+|z^{*}|-\ell +1]-1$    21    end if    22   end for    23   $R^{\prime }\left[1\right]=R\left[1\right]$    24   for j from 2 to k    25    $R^{\prime }\left[j\right]=R^{\prime }[j-1]+R\left[j\right]$    26   end for    27   % $T[i+j-1..i+j+\ell -2]$ is unique if and only if $R^{\prime }\left[j\right]=1$    28  end for    29 end for

5. Future Work

It seems straightforward to generalize our algorithms to find an SUS containing a given interval instead of a single position, or finding substrings whose Parikh vectors are unique, but it might be more challenging to generalize them to finding substrings whose elements’ relative order is unique, or to higher dimensions. Suppose that we want to find the smallest d-dimensional hypercube containing a given cell in a d-dimensional matrix, which occurs only once in that matrix. If the side lengths of the hypercube and matrix are L and n, respectively, then our approach seems to slow down by a factor of ${\left(Ln\right)}^{d-1}$. However, if we instead want to find the smallest d-dimensional hyperrectangle, then the slowdown seems to be more like $L^{2d}{n}^d$.