Faster Algorithms for Shortest Unique or Absent Substrings

We first establish two claims.

Assume, toward a contradiction, that the claim is false; that is, that we have $x^{\star }>0$ and there is no point $(x,y)\in P$ with $x=x^{\star }-1$. Let $p^{\star }=(x^{\star },y^{\star })$. By the definition of the primary skyline, $p^{\star }$ must be dominated by exactly one point in $P$. Now consider the point $p_{\text{left}}=(x^{\star }-1,y^{\star })$, which, due to the minimality of the coordinate-wise sum of $p^{\star }$, must be dominated by at least two points in $P$. Therefore, there exists a point $p^{\prime }\in P$ that dominates $p_{\text{left}}$ and does not dominate $p^{\star }$. Let $p^{\prime }=(x^{\prime },y^{\prime })$. Since $p^{\prime }$ does not dominate $p^{\star }$, we must have either or . We obtain a contradiction in each case:

• $\mathrm{■}$

  If , then by our assumption that no point $(x,y)\in P$ has $x=x^{\star }-1$, we must have $x^{\prime }\le x^{\star }-2$. Hence, , and thus $p^{\prime }$ does not dominate $p_{\text{left}}$, a contradiction.

• $\mathrm{■}$

  If , then $p^{\prime }$ clearly does not dominate $p_{\text{left}}$, a contradiction.

$\mathrm{⊲}$

By definition, $p^{\star }:=(x^{\star },y^{\star })$ is dominated by exactly one point, namely $p_{\text{unique}}$. Since points are only dominated by points weakly to their right, we have that $p_{\text{unique}}$ must be in $P^{\prime }$. We distinguish between two cases:

We have $P^{\prime }=\{p_{\text{unique}}\}$. If $y^{\star }>0$, then the point $p_{\text{down}}=(x^{\star },y^{\star }-1)$ is in ${\mathbb{Z}}_{\ge 0}^2$ and the only point of $P$ that dominates it is $p_{\text{unique}}$. Thus, $p_{\text{down}}$ lies in the primary skyline, but its coordinate sum $x^{\star }+y^{\star }-1$ is smaller than that of $p^{\star }$, contradicting the minimality of $p^{\star }$. Hence, $y^{\star }=0$.

Let $P_{\text{other}}=P^{\prime }\setminus \{p_{\text{unique}}\}$, and let $y^{\prime }$ be the maximum $y$-coordinate of a point in $P_{\text{other}}$. Since $p^{\star }$ is dominated uniquely by $p_{\text{unique}}$, every point $(x^{\prime \prime },y^{\prime \prime })\in P_{\text{other}}$ satisfies . Hence, . Conversely, since $p_{\text{unique}}$ dominates $p^{\star }$, its $y$-coordinate is at least $y^{\star }$. Therefore, the point $(x^{\star },y^{\star })$ is dominated by exactly one point in $P^{\prime }$ if and only if . By the minimality of $p^{\star }$, we have $y^{\star }=y^{\prime }+1$. $\mathrm{⊲}$

We assume, without loss of generality, that the points in $P$ are sorted by $x$-coordinate in non-decreasing order. We scan $P$ from right to left, while maintaining $y_{\max }$ and $y^{\prime }$, the two largest $y$-coordinates encountered among processed points (where $y_{\max }\ge y^{\prime }$). We initialize $y_{\max }$ and $y^{\prime }$ to $-1$, indicating that no processed point has contributed a valid $y$-coordinate yet.

We iterate through $P$ by grouping points with the same $x$-coordinate. Let $x_i$ denote the current $x$-coordinate of the group currently being processed, and let $P_{\text{curr}}=\{(x,y)\in P\mid x=x_i\}$ be the set of points at this coordinate. Before processing the points in $P_{\text{curr}}$, we evaluate the candidate $x$-coordinate $x^{\star }=x_i+1$. Because we have scanned from right to left, all points $(x,y)\in P$ such that $x\ge x^{\star }$ have already been processed. Let $P^{\prime }$ denote this set of previously processed points. We determine the corresponding $y^{\star }$ following Claim 23:

• $\mathrm{■}$

  If $|P^{\prime }|=1$, we set $y^{\star }=0$.

• $\mathrm{■}$

  If $|P^{\prime }|\ge 2$ and $y_{\max }>y^{\prime }$, we set $y^{\star }=y^{\prime }+1$.

• $\mathrm{■}$

  Otherwise (if $|P^{\prime }|=0$ or $y_{\max }=y^{\prime }$), the primary skyline does not intersect the set $\{(x^{\star },y)\mid y\in {\mathbb{Z}}_{\ge 0}\}$, so we skip this candidate.

After evaluating $y^{\star }$, we update $y_{\max }$ and $y^{\prime }$ using the $y$-values in $P_{\text{curr}}$ so that they remain the two largest $y$-coordinates among all processed points.

Finally, after all points in $P$ have been processed, we perform a last check for the candidate $x^{\star }=0$ using the final values of $y_{\max }$ and $y^{\prime }$. The algorithm maintains the candidate $(x^{\star },y^{\star })$ that minimizes $x^{\star }+y^{\star }$ and returns it as a witness. Each point of $P$ is processed exactly once using $𝒪(1)$ simple operations, thus the algorithm runs in $𝒪(|P|)$ time. $◀$

In the long aperiodic case (Section 3.2) and in the periodic case (Section 3.3), we show that a SUS of $S$ can be found by solving several instances of the Minimum Skyline Point problem. The core idea is to transform the SUS problem into a geometric one. Let us consider one such instance. We first identify a set $𝒮$ of carefully-selected substrings of $S$, each anchored around a common fragment $F=S[i..j]$. Each substring $U\in 𝒮$ is then represented by an integer point $(x,y)$, where $x$ and $y$ are the lengths of the extensions of $U$ to the left and the right, respectively, relative to the common fragment $F$.

Since strings in $𝒮$ are substrings of $S$ anchored around a common fragment, each point maps to one substring of $S$. Then, a string $U\in 𝒮$ is a substring of string $V\in 𝒮$ if and only if the point representing $U$ is dominated by the point representing $V$. To find a candidate SUS in $𝒮$, we look for a minimal extension anchored around $F$ that is contained within exactly one substring from $𝒮$. This is equivalent to solving a Minimum Skyline Point instance: finding an integer point $(x^{\star },y^{\star })$ that lies in the primary skyline of the points representing $𝒮$ that minimizes $x^{\star }+y^{\star }$. The total length of the resulting SUS is then $|F|+x^{\star }+y^{\star }$.

We begin by constructing a $\tau$-synchronizing set $\mathrm{𝐒𝐲𝐧𝐜}$ of $S$. Using this set, we construct two compacted tries $T$ and $T^R$. For every anchor $i\in \mathrm{𝐒𝐲𝐧𝐜}$, we insert the suffix $S[i..n)$ into $T$ and the reversed prefix $S{[0..i)}^R$ into $T^R$, labeling the corresponding leaves with the anchor $i$ in both tries. We make all implicit nodes in $T$ at string depth $k-1$ explicit. Hence, we have $N=𝒪(|\mathrm{𝐒𝐲𝐧𝐜}|)=𝒪(n/\tau )=𝒪(n/{\log }^{4}n)$.

Any fragment $P$ in $S$ that contains at least one anchor $i\in \mathrm{𝐒𝐲𝐧𝐜}$ can be decomposed into $P=\text{str}{(u)}^R\cdot \text{str}(v)$, where $u$ is a node in $T^R$ and $v$ is a node in $T$, both of which can be implicit. If $P$ has length at least $3\tau$ and period greater than $\frac{1}{3}\tau$, then by the definition of $\tau$-synchronizing sets, all occurrences of $P$ have anchors at the same relative positions. Specifically, any occurrence of $P$ starting at position $j$ must have $j+q\in \mathrm{𝐒𝐲𝐧𝐜}$ if and only if the original occurrence at position $i$ had an anchor at the same offset (Proposition 25). Thus, if the node pair $(u,v)$ represents the fragment $P$, the number of occurrences of $P$ is exactly $|L(u)\cap L(v)|$. To find a SUS, we must find a pair $(u,v)$ of (possibly implicit) nodes such that $|L(u)\cap L(v)|=1$ (uniqueness), $\text{sd}(v)\ge 2\tau$ (to satisfy the anchor offset property), and $\text{sd}(u)+\text{sd}(v)$ is minimized.

To do so, we set the weights of nodes in the two trees as follows. In both tries, we set the weight of the root node to $0$ and assign to each other node $u$ a weight $w(u):=\text{sd}(u)$. We thus create an instance of Two Trees SUS with $k=2\tau$. If the optimal node pair $(u,v)$ satisfies , we conclude that $S$ does not have a SUS of length $\mathrm{\ell }\ge 3\tau$ and period $p>\frac{1}{3}\tau$. (Note that since we have made all nodes with string depth $k-1$ explicit, for any node $v$ with $w(v)\ge k$, $v$’s parent has weight at least $k-1$, and hence $\max (w(\text{parent}(v)),k-1)=w(\text{parent}(v))$.) Otherwise, we return as a SUS the string $\text{str}{(u)}^R[0..w(\text{parent}(u))]\cdot \text{str}(v)[0..w(\text{parent}(v))]$ – the indices of the occurrence of this string in $S$ can be inferred from the common leaf label in the subtrees of $u$ and $v$.

The time complexity depends on the construction of the $\tau$-synchronizing set, which requires $𝒪(n/{\log }_{\sigma }n)$ time using Theorem 14, and the construction of the tries. For the tries, we first construct an LCE data structure over $S$ in $𝒪(n/{\log }_{\sigma }n)$ time [25] supporting $𝒪(1)$-time LCP queries. We sort the $N$ suffixes of $S$ in $𝒪(N\log N)$ time using merge sort, performing each comparison with an LCP query and a letter comparison. Given the sorted list of suffixes and the LCE data structure, the tries can then be constructed in $𝒪(N)$ time [24]. The total time for constructing the tries is $𝒪(n/{\log }_{\sigma }n)+𝒪(N\log N)\subseteq 𝒪(n/{\log }_{\sigma }n)$. $◀$

We analyze each case separately by aligning the occurrences of the Lyndon roots in $F$ and $F^{\prime }$ in all possible ways and comparing their extensions; see Figure 3 for illustrative examples. This allows us to determine if no alignment of $F$ is contained within $F^{\prime }$ (i.e., $F$ is not a substring of $F^{\prime }$), exactly one alignment is contained (unique substring), or multiple alignments are contained (not unique).

1. 1.

   If , we can align the first occurrence of the Lyndon root of $F$ with either the second or third occurrence of the Lyndon root of $F^{\prime }$. In both cases, both extensions of $F$ coincide with complete occurrences of the Lyndon root of $F^{\prime }$, meaning that $F$ is contained in both alignments and is therefore not a unique substring.

2. 2.

   If $e=e^{\prime }-2$, there are three possible alignments of the Lyndon roots. In the second alignment, both extensions of $F$ coincide with complete occurrences of the Lyndon root of $F^{\prime }$, so $F$ is a substring of $F^{\prime }$. In the first alignment, the left extensions of the runs are aligned, meaning that $F$ is contained in this alignment unless $\alpha >{\alpha }^{\prime }$. Similarly, in the third alignment, the same reasoning applies to the right extensions. Therefore, $F$ is a unique substring of $F^{\prime }$ if and only if $\alpha >{\alpha }^{\prime }$ and $\beta >{\beta }^{\prime }$.

3. 3.

   If $e=e^{\prime }-1$, there are two possible alignments. In the first alignment, the left extensions of the runs are aligned while the right extension of $F$ coincides with a complete occurrence of the Lyndon root of $F^{\prime }$; thus, $F$ is contained in this alignment if $\alpha \le {\alpha }^{\prime }$. The same reasoning applies symmetrically for the second alignment. Therefore, $F$ is a unique substring of $F^{\prime }$ if and only if either $\alpha >{\alpha }^{\prime }$ or $\beta >{\beta }^{\prime }$, but not both.

4. 4.

   If $e=e^{\prime }$, there is only one possible alignment of the Lyndon roots. For $F$ to be a substring of $F^{\prime }$, both extensions of $F$ must be shorter than or equal to those of $F^{\prime }$; that is, $\alpha \le {\alpha }^{\prime }$ and $\beta \le {\beta }^{\prime }$.

5. 5.

   If $e>e^{\prime }$, any alignment will result in an extension of $F^{\prime }$ being aligned with a Lyndon root of $F$; therefore, $F$ cannot possibly be a substring of $F^{\prime }$.

$◀$

For the following definitions, let ${ℛ}_{\lambda }$ be the set of $\tau$-runs in $S$ sharing the same Lyndon root $\lambda$. Let $r:=|\lambda |$, and let $e_{\lambda }^{\max }$ denote the maximum exponent among all $\tau$-runs in ${ℛ}_{\lambda }$.