Optimal Structure for Prefix-Substring Queries

For strings $r$ and $s$ with $|r|\le |s|$ we say that $r$ is a prefix (respectively, suffix) of $s$, if and only if $r=s[:|r|]$ (respectively, $r=s[|s|-|r|+1:]$); $r$ is a border of $s$, if and only if it is both a prefix and a suffix of $s$. We define $\text{Pref}(s):=\{\epsilon \}\cup \{s[:i]\mid i\in [|s|]\}$, $\text{Suff}(s):=\{\epsilon \}\cup \{s[i:]\mid i\in [|s|]\}$ and $\text{Bord}(s):=\text{Pref}(s)\cap \text{Suff}(s)$ as the sets of prefixes, suffixes and borders of $s$ respectively. For $y\in [|s|]$, we say that the prefix $s[:y]$ is the prior of the suffix $s[y+1:]$ and that the suffix $s[y+1:]$ is the posterior of the prefix $s[:y]$.

Given some , we say that $s$ is $p$-periodic, if and only if $s[i]=s[i+p]$ for all $i\in [|s|-p]$. Note that this is equivalent to the condition $s[:|s|-p]=s[1+p:]$, meaning that $s$ is $p$-periodic if and only if $s$ has a border of length $|s|-p$. We say that the period $\mathrm{per}(s)$ of $s$ is the smallest value of $p$ such that $s$ is $p$-periodic or $\mathrm{\infty }$ if there is no such value. In the latter case, we also say that $s$ is aperiodic. The following lemma is well-known [18].

Using this lemma, we can derive the following properties about borders and their periods. The proofs of these three results are given in Appendix A, for completeness.

Let ${\text{Bord}}_p(s):=\{r\mid r\in \text{Bord}(s),\mathrm{per}(r)=p\}$ denote the set of borders of $s$ with period $p$.

We assume the standard unit-cost word RAM with logarithmic word-size $\omega$ (so each memory word consists of $\omega \ge \log n$ bits). Standard arithmetical and bitwise operations (and indirect addressing) on such words are assumed to take $𝒪(1)$ time [12]. We assume that our input is over a polynomial alphabet, i.e., $|\mathrm{\Sigma }|\in n^{𝒪(1)}$, where $n$ is the length of the input string. We refer to a structure that can be stored in $𝒪(n)$ memory words as linear-space.

For string $s$, with $|s|=n$, and $i,j\in [n]$, let ${\text{LCP}}_s(i,j):=\max \{|r|\mid r\in \text{Pref}(s[i:])\cap \text{Pref}(s[j:])\}$ be the length of the longest common prefix of $s[i:]$ and $s[j:]$.

Using this data structure, we can also find longest periodic prefixes. Given some $p\in [n-1]$, we can calculate $\mathrm{\ell }={\text{LCP}}_s(i,i+p)$, if $\mathrm{\ell }>0$ we have $s[i:i+\mathrm{\ell }-1]=s[i+p:i+\mathrm{\ell }+p-1]$ and $s[i+\mathrm{\ell }]\ne s[i+p+\mathrm{\ell }]$, meaning that $s[i:i+\mathrm{\ell }+p-1]$ is the longest $p$-periodic prefix of $s[i:]$. By constructing the data structure for $s^R$, we can similarly determine longest common suffixes and longest periodic suffixes.

For some string $s$ of length $n$, the suffix tree of $s$ is a compressed trie $T=(V,E)$, i.e., a tree with the following properties:

• $\mathrm{■}$

  Each edge is labeled with some non-empty string over the alphabet $\mathrm{\Sigma }\cup \$$ with $\$\notin \mathrm{\Sigma }$ being a special character.

• $\mathrm{■}$

  The labels of any two edges starting at the same node do not share a common prefix.

• $\mathrm{■}$

  Each inner node has at least two children.

Let $v\in V$ be some node and let $s_1,\mathrm{\dots },s_m$ be the labels of the path from the root to $v$. We now define $\text{Strings}(v):=\{s_1\mathrm{\cdots }{s}_{m-1}r\mid r\in \text{Pref}(s_m)\setminus \{\epsilon \}\}$ as the set of strings corresponding to $v$, for the root node $v_r$ it is $\text{Strings}(v_r)=\{\epsilon \}$. The defining property of the suffix tree is now that ${\bigcup }_{v\in V}\text{Strings}(v)=\text{Substr}(s\$)$. We use the following results for the suffix tree:

For any $i,j\in [n]$, there is exactly one node $v$ in the suffix tree of $s$ such that $s[i:j]\in \text{Strings}(v)$. We write $v={\text{SuffNode}}_s(i,j)$ and call $v$ the node corresponding to the substring $s[i:j]$.

We also use the following standard observation:

In this paper, we take the relations “is ancestor of” and “is descendant of” to be reflexive, i.e., a node is both its own ancestor and its own descendant, unless explicitly noted otherwise.

The following result is shown in Appendix A.

For some string $s$ of length $n$, the border tree of $s$ is defined as follows. The nodes of the tree correspond one-to-one to the prefixes of $s$ and for any node $v$ corresponding to some prefix $r\ne \epsilon$, the parent of $v$ is the node that corresponds to the longest border of $r$. This is well defined, because $\text{Bord}(r)$ always contains at least $\epsilon$ and any border of $r$ is a prefix of $r$ and therefore also a prefix of $s$. The node corresponding to $\epsilon$ has no parent and is the root node of the tree. The border tree can now be compressed by grouping the borders by their periodicities (on each path). From Lemma 4 it follows that we can encode each group of borders as an arithmetic progression using constant space. The compressed border tree then has depth $𝒪(\log n)$ as seen in Lemma 3.

From the definition of the border tree, it follows that for some prefix $r\in \text{Pref}(s)$, the ancestors of the node corresponding to $r$ in the border tree correspond exactly to the borders of $r$. For the compressed version of the border tree, this is not true anymore. Consider some section on some path, where all nodes correspond to prefixes with the same periodicity. During compression, this section is replaced with a single node. In this process, all nodes that were children of any node in the section become children of the new compressed node, even though they have different sets of ancestors. In particular, from the arithmetic progression of prefixes that is represented by their new parent, only the prefixes up to some length are actual borders. We can determine this length, for some node $v$, by taking the smallest prefix $r$ associated with $v$, the longest border of which has to have length $|r|-\mathrm{per}(r)$, we can then trim the arithmetic progression corresponding to the parent of $v$, removing all prefixes longer than this value.

Given two trees $T_1=(V_1,E_1)$ and $T_2=(V_2,E_2)$, we can relate these trees to each other by using a common set of labels. Hereby, each label gets assigned to one node from each tree. We then say that two nodes $v_1\in V_1$ and $v_2\in V_2$ are induced, if and only if there are descendants $u_1$ of $v_1$ and $u_2$ of $v_2$ that share the same label. The partner of $v_1$ with respect to $v_2$, denoted $\text{partner}(v_1/v_2)$, is the lowest ancestor $v_2^{\prime }$ of $v_2$, such that $v_1$ and $v_2^{\prime }$ are induced.

Given a tree, we can decompose it, as follows. First, we select a subset of the nodes from the tree, including the root node. We call these nodes special. For each special node $u$, we partition its children into non-empty sets. Each set of siblings corresponds to one fragment of the decomposition, containing the siblings, their parent $u$ (which becomes the root node of the fragment), and all their descendants which have $u$ as their lowest special ancestor. Since the root node is special, each node has a special ancestor and each non-special node belongs to exactly one fragment. Therefore, we obtain a set of micro-trees (the fragments) and a macro-tree that consists only of the special nodes, arranged as to preserve the ancestor/descendant relations between each pair of node. It is possible to construct such a decomposition for any desired fragment size efficiently (even though this is well known – see [11], for instance – we give a proof in Appendix A, fitting to our setting, for completeness):

We also use the following well known data structures.

Clearly, the non-crossing matches are exactly the borders of $s[:k]$ of length at most $|s[j:k]|$. Thus, determining the length of the longest non-crossing match, ${\text{PrefSubstr}}_s^{nc}(i,j,k)$, is equivalent to determining the length of the longest such border of $s[:k]$. Each such match $s[:x]$ satisfies that ${(s[:x])}^R$ is a prefix of ${(s[j:k])}^R$ and a suffix of $s^R$, so the longest match can then be found in the suffix tree of $s^R$ as the lowest ancestor of the node corresponding to ${(s[j:k])}^R$, that corresponds to a suffix. Determining this is possible in $𝒪(1)$ time.

For crossing match $s[:x]\in {\text{PrefSubstrMatches}}_s^c(i,j,k)$, we can split the match at $y=x-|s[j:k]|$, such that $s[:y]$ is a suffix (and as such, a border) of $s[:i]$ and $s[y+1:]$ has prefix $s[j:k]$. We then say that $s[:y]$ induces the match $s[:x]$. Like this, PrefixSubstringQueries can be rephrased as: “Find the longest border $s[:y]$ of $s[:i]$ such that its posterior starts with $s[j:k]$”. By checking, for each border $s[:y]$ of $s[:i]$ individually, whether $s[y+1:]$ has prefix $s[j:k]$, we obtain a naive algorithm that answers queries in $𝒪(n)$ time, after $𝒪(n)$ time preprocessing. This can be optimized by exploiting the structure of the borders, yielding an algorithm with $𝒪(\log n)$ query time, after $𝒪(n)$ preprocessing.

Sticking with our approach to find the longest $y\in [n]$, such that $s[:y]$ is a border of $s[:i]$ and $s[y+1:]$ has prefix $s[j:k]$, we observe that this can be expressed as a problem on the border and suffix tree, as follows. Labeling the node $v_y$ corresponding to $s[:y]$ in the border tree and the node ${\text{SuffNode}}_s(y+1,n)$ in the suffix tree with label $y$ for each $y\in [n]$, we then want to find the largest label $y$ such that the node labeled with $y$ in the border tree is an ancestor of the node corresponding to $s[:i]$ and the node labeled with $y$ in the suffix tree is a descendant of ${\text{SuffNode}}_s(j,k)$. This is quite similar to solving $\text{partner}({\text{SuffNode}}_s(j,k)/v_i))$, only that the result $v_{i^{\prime }}$ of this query is only guaranteed to have a descendant with a label $y^{\prime }$ that also occurs in the descendants of ${\text{SuffNode}}_s(j,k)$, instead of having such a label itself. Still, it turns out that the matches are exactly the borders of $s[:y^{\prime }+t]$ of length at most $i^{\prime }+t$, meaning that the longest match can be found similarly as the non-crossing matches. Apart from solving the partner query, this reduction only requires linear preprocessing and constant query time.

To obtain a constant time solution for crossing matches, we split the borders $s[:y]$ of $s[:i]$ into three groups:

• $\mathrm{■}$

  For $y\le t:=|s[j:k]|$, the set of such $y$ satisfying that the posterior $s[y+1:]$ has prefix $s[j:k]$ is an arithmetic progression with some step $p$. We can find the longest such $s[:y]$ that induces a match by comparing the lengths of the longest $p$-periodic suffixes of $s[:i]s[j:k]$ and $s[:y+t]$ for all such $y$, using the fact that each $s[:y+t]$ has a different such length.

• $\mathrm{■}$

  For $y>t$ and , we observe that the borders $s[:y]$ of $s[:i]$ with this condition only have a constant number of different periodicities. For each periodicity $p$, we can in constant time determine the longest induced match, using the same method with which we optimized the initial naive algorithm.

• $\mathrm{■}$

  For $\mathrm{per}(s[:y])\ge t$, we see that almost all (all, but the longest) prefixes $s[:y]$ with some shared periodicity $p=\mathrm{per}(s[:y])\ge t$ share a common prefix of length $t$ and therefore, for each such periodicity $p$, we only need to consider two candidates for inducing the longest match and in total, we consider $𝒪(\log n)$ candidates. If we sort them in the preorder of their respective posteriors in the suffix tree, all candidate prefixes that induce a match lie in some interval of this list, corresponding to the preorder interval representing the subtree rooted in ${\text{SuffNode}}_s(j,k)$. We can then find this interval using fusion trees and the longest match in the interval using an RMQ query.

While this enables us to answer queries in constant time, the last case requires maintaining $𝒪(\log n)$-sized data structures for each prefix of $s$. To avoid this, we perform a micro-macro decomposition of the border tree with fragment size $\lfloor \log n\rfloor$ and then only build these data structures for the prefixes corresponding to the $𝒪(n/\log n)$ special nodes. For some query $(i,j,k)\in \text{PrefSubstrQueries}(s)$, we find the fragment containing the node $v_i$ corresponding to $s[:i]$ and its special root $u_i$. We then check all borders corresponding to ancestors of $u_i$, using the method from above. The remaining borders of $s[:i]$ correspond to ancestors of $v_i$ in that fragment. The subset of these borders that induce a match can be expressed as an interval in 3D space, with the dimensions being the preorder and postorder indices of the corresponding nodes in the fragment and the preorder index of the posterior in the suffix tree. Since there are at most $𝒪(\log n)$ such borders, we can encode sets of borders in a constant number of machine words and use bit operations to operate on the sets. This allows for an $𝒪(1)$ time solution, using $𝒪(\log n)$ preprocessing per fragment, i.e., $𝒪(n)$ preprocessing time in total.

Combining this with Lemma 20, addressing non-crossing matches, we obtain the following.

Note that we only consider here queries $(i,j,k)$ with $i\ge 1$. In fact, our algorithm addressing non-crossing matches can be canonically used to answer queries $(0,j,k)$, so the statement of Theorem 18 holds also for all queries of the form $(0,j,k)$, with $1\le j\le k\le n$.

We construct the suffix tree of $s^R$. The desired solution $x$ satisfies that ${(s[:x])}^R$ is the longest suffix of $s^R$ that is also a prefix of ${(s[j:k])}^R$. In terms of the suffix tree, determining this corresponds to finding the lowest ancestor of ${\text{SuffNode}}_{s^R}(n-k+1,n-j+1)$ that corresponds to a suffix of $s$; this ancestor can be precomputed for every node. $◀$

By setting $\mathrm{\ell }=|s[j:k]|=k-j+1$, we obtain the following lemma.