Space-Efficient Online Computation of String Net Occurrences

Let $\mathrm{\Sigma }$ be an alphabet of size $\sigma$. An element of $\mathrm{\Sigma }$ is called a character. An element of ${\mathrm{\Sigma }}^{\star }$ is called a string. The empty string $\epsilon$ is the string of length $0$. If $T=pfs$ holds for strings $T,p,f$, and $s$, then $p,f$, and $s$ are called a prefix of $T$, a substring of $T$, and a suffix of $T$, respectively. A prefix $p$ (resp. a suffix $s$) of $T$ is called a proper prefix (resp. a proper suffix) of $T$ if $p\ne T$ (resp. $s\ne T$). For a string $T$, $|T|$ denotes the length of $T$. For a string $T$ and an integer $i$ with $1\le i\le |T|$, $T[i]$ denotes the $i$th character of $T$. For a string $T$ and integers $i,j$ with $1\le i\le j\le |T|$, $T[i..j]$ denotes the substring of $T$ starting at position $i$ and ending at position $j$. For strings $T$ and $w$, we say $w$ occurs in $T$ if $T[i..j]=w$ holds for some $i,j$. Also, if such $i,j$ exist, we denote by $[i..j]$ the occurrence of $w=T[i..j]$ in $T$. Also, we denote by ${\mathrm{𝑜𝑐𝑐}}_T(w)$ the set of occurrences of $w$ in $T$, i.e., ${\mathrm{𝑜𝑐𝑐}}_T(w)=\{[i..j]\mid T[i..j]=w\}$. For any set $S$, we denote by $\mathrm{\#}S$ the cardinality of $S$. For convenience, we assume that the empty string $\epsilon$ occurs $|T|-1$ times at the boundaries of consecutive characters in $T$, and denote these inner occurrences by $T[i+1..i]=\epsilon$ for . We also assume that $\epsilon$ occurs before the first character and after the last character of $T$. Thus we have $\mathrm{\#}{\mathrm{𝑜𝑐𝑐}}_T(\epsilon )=|T|+1$. A string $w$ is said to be unique in $T$ if $\mathrm{\#}{\mathrm{𝑜𝑐𝑐}}_T(w)=1$. Also, $w$ is said to be quasi-unique in $T$ if $1\le \mathrm{\#}{\mathrm{𝑜𝑐𝑐}}_T(w)\le 2$. Further, $w$ is said to be repeating in $T$ if $\mathrm{\#}{\mathrm{𝑜𝑐𝑐}}_T(w)\ge 2$. We denote by $\mathrm{𝑙𝑟𝑆𝑢𝑓}(T)$ (resp. $\mathrm{𝑙𝑟𝑃𝑟𝑒𝑓}(T)$) the longest repeating suffix (resp. prefix) of $T$. We denote by $\mathrm{𝑠𝑞𝑆𝑢𝑓}(T)$ (resp. $\mathrm{𝑠𝑞𝑃𝑟𝑒𝑓}(T)$) the shortest quasi-unique suffix (resp. prefix) of $T$.

A repeating substring of a string $T$ is also called a repeat in $T$. A repeat $u$ in $T$ is said to be left-branching in $T$ if there are at least two distinct characters $a,a^{\prime }\in \mathrm{\Sigma }$ such that $\mathrm{\#}{\mathrm{𝑜𝑐𝑐}}_T(au)\ge 1$ and $\mathrm{\#}{\mathrm{𝑜𝑐𝑐}}_T(a^{\prime }u)\ge 1$. Symmetrically, a repeat $u$ is said to be right-branching in $T$ if there are at least two distinct characters $b,b^{\prime }\in \mathrm{\Sigma }$ such that $\mathrm{\#}{\mathrm{𝑜𝑐𝑐}}_T(ub)\ge 1$ and $\mathrm{\#}{\mathrm{𝑜𝑐𝑐}}_T(u{b}^{\prime })\ge 1$. A repeat $u$ of $T$ is said to be left-maximal in $T$ if $u$ is a left-branching repeat of $T$ or $u$ is a prefix of $T$, and $u$ is said to be right-maximal in $T$ if $u$ is a right-branching repeat in $T$ or $u$ is a suffix of $T$. A repeat $u$ of $T$ is said to be maximal in $T$ if $u$ is both a left-maximal repeat and a right-maximal repeat in $T$. Let $\mathrm{𝖫𝖡}(T)$, $\mathrm{𝖱𝖡}(T)$, $\mathrm{𝖫𝖬}(T)$, $\mathrm{𝖱𝖬}(T)$, and $𝖬(T)$ denote the sets of left-branching, right-branching, left-maximal, right-maximal, and maximal repeats in $T$, respectively. Note that $\mathrm{𝖫𝖡}(T)\subseteq \mathrm{𝖫𝖬}(T)$, $\mathrm{𝖱𝖡}(T)\subseteq \mathrm{𝖱𝖬}(T)$, and $𝖬(T)=\mathrm{𝖫𝖬}(T)\cap \mathrm{𝖱𝖬}(T)$ hold. A unique substring $u=T[i..j]$ of a string $T$ is said to be a minimal unique substring (MUS) of $T$ if each of the substrings $T[i+1..j]$ and $T[i..j-1]$ is a repeat in $T$. By definition, no MUS can be completely contained in another MUS in the string, and thus, there are at most $n$ MUSs in any string $T$ of length $n$. Let $\mathrm{𝖬𝖴𝖲}(T)$ denote the set of occurrences of all MUSs in $T$.

In what follows, we fix a string $T$ of length $n>2$ arbitrarily.

For a repeating substring $P$ of $T$, its occurrence $[i..j]$ in $T$ is said to be a net occurrence of $P$ if $T[i-1..j]$ is unique in $T$, and $T[i..j+1]$ is unique in $T$. Let $\mathrm{𝖭𝖮}(T)$ be the set of net occurrences in $T$. We call $T[i-1..j+1]$ a net unique substring (NUS) if $[i..j]\in \mathrm{𝖭𝖮}(T)$. Let $\mathrm{𝖭𝖴𝖲}(T)$ be the set of net unique substrings in $T$. Then, we call the occurrence $[i-1..j+1]$ of NUS $T[i-1..j+1]$ the extended net occurrence of the repeat $T[i..j]$. Let $\mathrm{𝖤𝖭𝖮}(T)$ be the set of extended net occurrences in $T$. Clearly, there is a one-to-one correspondence between $\mathrm{𝖭𝖴𝖲}(T)$ and $\mathrm{𝖤𝖭𝖮}(T)$, i.e., $T[p..q]\in \mathrm{𝖭𝖴𝖲}(T)$ iff $[p..q]\in \mathrm{𝖤𝖭𝖮}(T)$. Note that $\mathrm{\#}\mathrm{𝖤𝖭𝖮}(T)=\mathrm{\#}\mathrm{𝖭𝖮}(T)$ holds.

The suffix tree [23] of a string $T$ is a compacted trie that represents all suffixes of $T$. More formally, the suffix tree of $T$ is a rooted tree such that (1) each edge is labeled by a non-empty substring of $T$, (2) the labels of the out-edges of the same node begin with distinct characters, and (3) every suffix of $T$ is represented by a path from the root. If the path from the root to a node $v$ spells out the substring $w$ of $T$, then we say that the node $v$ represents $w$. By representing each edge label $x$ with a pair $(i,j)$ of positions such that $x=T[i..j]$, the suffix tree can be stored in $O(n)$ space. For convenience, we identify each node with the string that the node represents. If $av$ is a node of the suffix tree with $a\in \mathrm{\Sigma }$ and $v\in {\mathrm{\Sigma }}^{\star }$, then the suffix link of the node $av$ points to the node $v$.

There are two versions of suffix trees, implicit suffix trees [22] (a.k.a. Ukkonen trees) and explicit suffix trees [23] (a.k.a Weiner trees). In the implicit suffix tree of string $T$, each repeating suffix $s$ of $T$ that has a unique right-extension $c\in \mathrm{\Sigma }$ (namely, $\mathrm{\#}{\mathrm{𝑜𝑐𝑐}}_T(sc)\ge 1$ and $\mathrm{\#}{\mathrm{𝑜𝑐𝑐}}_T(sa)=0$ for any $a\in \mathrm{\Sigma }\setminus \{c\}$) is represented on an edge. On the other hand, each such repeating suffix is represented by a non-branching internal node in the explicit suffix tree of $T$. Let ${\mathrm{𝖲𝖳𝗋𝖾𝖾}}^{\prime }(T)$ and $\mathrm{𝖲𝖳𝗋𝖾𝖾}(T)$ denote the implicit suffix tree and the explicit suffix tree of string $T$, respectively. The internal nodes of ${\mathrm{𝖲𝖳𝗋𝖾𝖾}}^{\prime }(w)$ represent the right-branching repeats of $T$, while the internal nodes of $\mathrm{𝖲𝖳𝗋𝖾𝖾}(w)$ represent the right-maximal repeats of $T$. It is thus clear that ${\mathrm{𝖲𝖳𝗋𝖾𝖾}}^{\prime }(T\$)=\mathrm{𝖲𝖳𝗋𝖾𝖾}(T\$)$ with a unique end-marker $\$$ that does not occur in $T$. Due to the nature of left-to-right online string processing, we will use the implicit suffix trees in our algorithms.

The compact directed acyclic word graph (CDAWG) [2] of a string $T$ is the smallest edge-labeled DAG that represents all substrings of $T$. There are two versions of CDAWGs as well, implicit CDAWGs [9] and explicit CDAWGs [2]. The implicit CDAWG of string $T$, denoted ${\mathrm{𝖢𝖣𝖠𝖶𝖦}}^{\prime }(T)$, is the edge-labeled DAG that is obtained by merging all isomorphic subtrees of the implicit suffix tree ${\mathrm{𝖲𝖳𝗋𝖾𝖾}}^{\prime }(T)$ which are connected by suffix links. On the other hand, the explicit CDAWG of $T$, denoted $\mathrm{𝖢𝖣𝖠𝖶𝖦}(T)$, is the edge-labeled DAG that is obtained by merging all isomorphic subtrees of the explicit suffix tree $\mathrm{𝖲𝖳𝗋𝖾𝖾}(T)$ which are connected by suffix links. The internal nodes of ${\mathrm{𝖢𝖣𝖠𝖶𝖦}}^{\prime }(T)$ have a one-to-one correspondence with the left-maximal and right-branching repeats in $T$, while the internal nodes of $\mathrm{𝖢𝖣𝖠𝖶𝖦}(T)$ have a one-to-one correspondence with the maximal repeats in $T$. More precisely, the longest string represented by an internal node in ${\mathrm{𝖢𝖣𝖠𝖶𝖦}}^{\prime }(T)$ is a left-maximal and right-branching repeat in $T$, and the longest string represented by an internal node in $\mathrm{𝖢𝖣𝖠𝖶𝖦}(T)$ is a maximal repeat in $T$. Thus, as in the case of suffix trees, ${\mathrm{𝖢𝖣𝖠𝖶𝖦}}^{\prime }(T\$)=\mathrm{𝖢𝖣𝖠𝖶𝖦}(T\$)$ holds with a unique end-marker $\$$.

The length of a path in the implicit/explicit CDAWG is the total length of the labels of the edges in the path. An in-edge of a node $v$ in the implicit/explicit CDAWG is said to be a primary edge if it belongs to the longest path from the source to $v$.

Due to the nature of left-to-right online string processing, we will use the implicit CDAWGs in our algorithm. Let ${𝖾}^{\prime }(T)$ and $𝖾(T)$ denote the number of edges of ${\mathrm{𝖢𝖣𝖠𝖶𝖦}}^{\prime }(T)$ and $\mathrm{𝖢𝖣𝖠𝖶𝖦}(T)$, respectively. The following lemma guarantees that the worst-case space complexity of our implicit-CDAWG based algorithm is linear in the size of explicit CDAWGs: