Compressed Dictionary Matching on Run-Length Encoded Strings

We address the basic question of whether it is possible to solve compressed dictionary matching in near-linear time in the total number of runs in the input. We show the following main result.

Theorem 1 assumes a standard word-RAM model of computation with logarithmic word length, and space is the number of words used by the algorithm, excluding the input strings, which are assumed to be read-only.

This is the first non-trivial algorithm for compressed dictionary matching on run-length encoded strings. Since any solution must read the input the time bound of Theorem 1 is optimal within a $\log \log m$ factor.

Our starting point is the classic Aho-Corasick algorithm for dictionary matching [1] that generalizes the Knuth-Morris-Pratt algorithm [42] for single string matching to multiple strings. Given a set of pattern strings $𝒫=\{P_1,\mathrm{\dots },P_k\}$ of total length $m$ the Aho-Corasick automaton (AC automaton) for $𝒫$ consists of the trie of the patterns in $𝒫$. Hence, any path from the trie’s root to a node $v$ corresponds to a prefix of a pattern $P\in 𝒫$. For each node $v$, a special failure link points to the node corresponding to the longest prefix matching a proper suffix of the string identified by $v$ and an output link that points to the node corresponding to the longest pattern that matches a suffix of the string identified by $v$.

To solve dictionary matching, we read $S$ one character at a time and traverse the AC automaton. At each step, we maintain the node corresponding to the longest suffix of the current prefix of $S$. If we cannot match a character, we recursively follow failure pointers (without reading further in $S$). If we reach a node with an output link, we output the corresponding pattern and recursively follow output links to report all other patterns matching at the current position in $S$. If we implement the trie using perfect hashing [35], we can perform the top-down traversal in constant time per character. Since failure links always point to a node of strictly smaller depth in the trie, it follows that we can charge the cost of traversing these to reading characters in $S$, and thus, the total time for traversing failure links is $O(n)$. Each traversal of an output link results in a reported occurrence, and thus, the total time for traversing output links is $O(\mathrm{occ})$. In total, this leads to a solution to dictionary matching that uses $O(m)$ space and $O(n+m+\mathrm{occ})$ expected time.

At a high level, our main result in Theorem 1 can viewed as a compressed implementation of the AC-automaton, that implements dictionary matching $O((\overline{m}+\overline{n})\log \log m+\mathrm{occ})$ expected time and $O(\overline{m})$ space. Compared to the uncompressed AC-automaton, we achieve the same bound in the compressed input except for a $\log \log m$ factor in the time complexity.

To implement the AC automaton in $O(\overline{m})$ space, we introduce the run-length encoded trie $T_{\text{RLE}}$ of $𝒫$, where each run ${\alpha }^x$ in a pattern $P\in 𝒫$ is encoded as a single letter “${\alpha }^x$” and show how to simulate the action of the Aho-Corasick algorithm on $T_{\text{RLE}}$ processing one run of $S$ at a time. The key challenge is that the nodes in the AC automaton are not explicitly represented in $T_{\text{RLE}}$, and thus, we cannot directly implement the failure and output links in $T_{\text{RLE}}$.

Naively, we can simulate the failure links of the AC automaton directly on $T_{\text{RLE}}$. However, as in the Aho-Corasick algorithm, this leads to a solution traversing $\mathrm{\Omega }(n)$ failure links, which we cannot afford. Instead, we show how to efficiently construct a data structure to group and process nodes simultaneously, achieving $O(\overline{n}\log \log m)$ total processing time.

Similarly, we can simulate the output links by grouping them at the explicit nodes, but even on a simple instance such as $𝒫=\{a,a^{m-1}\}$ this would result in $\mathrm{\Omega }(m)$ output links in total which we also cannot afford. Alternatively, we can store a single output link for each explicit node as in the AC automaton. However, the occurrences we need to report are not only patterns that are suffixes of the string seen until now, but also patterns ending inside the last processed run. Not all occurrences ending in the last run are substrings of each other, and thus, saving only the longest is not sufficient. Instead, we reduce the problem of reporting all occurrences that end in a specific run of $S$ to a new data structure problem called truncate match reporting problem. To solve this problem, we reduce it to a problem of independent interest on colored weighted trees called colored ancestor threshold reporting. We present an efficient solution to the truncate match reporting problem by combining several existing tree data structures in a novel way, ultimately leading to the final solution.

Along the way, we also develop a simple and general technique for compressed sorting of run-length encoded strings of independent interest, which we need to preprocess our pattern strings efficiently.

In Section 3, we show how to efficiently sort run-length encoded strings and subsequently efficiently construct the corresponding compact trie. In Section 4 we introduce the truncate match reporting and colored ancestor threshold reporting problem, our efficient solution to the colored ancestor threshold reporting problem, and our reduction from the truncate match reporting problem to the colored ancestor threshold reporting problem. In Section 5, we first give a simple and inefficient version of our algorithm, that focuses on navigation the run-length encoded trie. Finally, in Section 6, we extend and improve the simple version of our algorithm to achieve our main result.

To sort the strings $𝒫$, we construct the set of strings $\widetilde{𝒫}=\{{\tilde{P}}_1,\mathrm{\dots },{\tilde{P}}_k\}$ such that ${\tilde{P}}_i=({\alpha }_1,x_1)({\alpha }_2,x_2)\mathrm{\cdots }$ is the sequence of the runs in $\overline{P_i}={\alpha }_1^{x_1}{\alpha }_2^{x_2}\mathrm{\cdots }$, represented as pairs of character and length. We say that a pair $(\alpha ,x)$ is smaller than $(\beta ,y)$ if or . Assume that we have the compact trie $\tilde{T}$ of $\widetilde{𝒫}$, where the edges are lexicographically sorted by their edge labels. We will show that we can construct the compact trie $T$ of $𝒫$ from $\tilde{T}$ in $O(\overline{m})$ time and maintain the ordering of the edges. Observe that for a node in $v\in T$ the ordering of edge labels of the children of $v$ are equivalent to the ordering achieved by encoding them as pairs of character and length, since the first character of each edge would differ. Let $w$ be an internal node in $T$ such that there is no node $\tilde{w}\in \tilde{T}$ where $s_w=s_{\tilde{w}}$. Since $w$ is an internal node in $T$, two patterns $P_i$ and $P_j$ exist such that the longest common prefix of $P_i$ and $P_j$ is $s_w$. Since $w$ does not have a corresponding node in $\tilde{T}$, then there must exists a node $\tilde{w}$ in $\tilde{T}$ such that $s_w=s_{\tilde{w}}{\beta }^y$ with at least two children with edge labels $(\beta ,y)Y$ and $(\beta ,z)Z$ where . We ensure that any node $w\in T$ has a corresponding node in $\tilde{T}$ as follows. Starting at the root of $\tilde{T}$, we do the following at each node $v$. Let $v_1,v_2,\mathrm{\dots },v_d$ be the children of $v$ lexicographically ordered by their edge labels $({\beta }_1,y_1)Y_1,({\beta }_2,y_2)Y_2,\mathrm{\dots },({\beta }_d,y_d)Y_d$. Starting at $i=d$ we do the following.

• $\mathrm{■}$

  If ${\beta }_{i-1}={\beta }_i$ and $Y_{i-1}$ is not the empty string, we insert a node $w$ on the edge to $v_{i-1}$ and make $v_i$ the child of $w$. We then set the edge label of edge $(v,w)$, $(w,v_{i-1})$, and $(w,v_i)$ to $({\beta }_i,y_{i-1})$, $Y_{i-1}$, and $({\beta }_i,y_i-y_{i-1})Y_i$, respectively.

• $\mathrm{■}$

  If ${\beta }_{i-1}={\beta }_i$ and $Y_{i-1}$ is the empty string, we make $v_i$ the child of $v_{i-1}$ and set the edge label of $(v_{i-1},v_i)$ to $({\beta }_i,y_i-y_{i-1})Y_i$.

Note that if $Y_{i-1}$ is empty, then no child of $v_{i-1}$ will have $({\beta }_i,z)$ as the first character on their edge label, since it could then be encoded as $({\beta }_i,y_{i-1}+z)$. Hence, the parent of $v_i$ cannot change again. To maintain the order of the children of $v_i$ and $w$, we insert new edges using insertion sort. When $w$ is created, it takes $v_{i-1}$’s place in the ordering of the children of $v$. We then decrement $i$ until $i=1$ and then recurse on the remaining children of $v$. Finally, we traverse $\tilde{T}$ and remove non-root vertices with only a single child. Since the children already appear in sorted order, we can recover the sorted order of $𝒫$ from the constructed compact trie. We use $O(t(k,\overline{m},\sigma \cdot m)+\overline{m})$ time and $O(s(k,\overline{m},\sigma \cdot m)+\overline{m})$ space to sort $\widetilde{𝒫}$. We can construct $\tilde{T}$ from the sorted sequence of $\widetilde{𝒫}$ in $O(\overline{m})$ time (see Appendix A for the proof). We insert at most $O(k)$ nodes in $\tilde{T}$, and we apply insertion sort $O(1)$ time at each node. Hence, we use $O(\overline{m})$ time doing the insertion sort. In summary, we have shown Lemma 3. $◀$

Andersson and Nilsson [14] showed how to sort strings in $t(k,m,\sigma )=O(m+k\log \log k)$ expected time and $s(k,m,\sigma )=O(m)$ space. We obtain the following result by plugging this into Lemma 3.

Using Corollary 4 and Lemma 3 we can efficiently construct the compact trie of $𝒫$ from $\overline{𝒫}$.

For a node $v$ in the trie $T_{\text{RLE}}$, let $s_v$ denote the string obtained by concatenating the characters of the edges of the root-to-$v$ path where a run is not considered as a single letter. We store the following for each node $v$ in $T_{\text{RLE}}$:

• $\mathrm{■}$

  $D_v$: A dictionary of the children of $v$, with their edge labels as key.

• $\mathrm{■}$

  $F_v$: A failure link to the node $u$ in $T_{\text{RLE}}$ for which $s_u$ is the longest proper suffix of $s_v$. We define the failure link for the root to be itself.

• $\mathrm{■}$

  $i_v$: The pattern index such that pattern $P_{i_v}^{\prime }$ is the longest suffix of $s_v$ among all truncated patterns. If no such pattern exists let $i_v=-1$.

We build the truncate match reporting data structure for the set $𝒫$. Finally, for each pattern $P_i=P_i^{\prime }{\alpha }_i^{x_i}$ we store its length $|P_i|$ and the length $x_i$ of the last run of $P_i$. See Figure 3 for an example.

The number of edges and nodes in $T_{\text{RLE}}$ is $O(\overline{m})$. The dictionaries and failure links associated with $T_{\text{RLE}}$ use space proportional to the number of edges and vertices in $T_{\text{RLE}}$, hence $O(\overline{m})$ space. By Lemma 7 the truncate match reporting data structure uses $O(k)$ space. In total, we use $O(\overline{m}+k)=O(\overline{m})$ space.

Given a run-length encoded string $S$ we report all locations of occurrences of the patterns $𝒫$ in $S$ as follows. We process $S$ one run at a time. Let $S^{\prime }$ be the processed part of $S$. We maintain the node $v$ in $T_{\text{RLE}}$ such that $s_v$ is the longest suffix of $S^{\prime }$. Initially, $S^{\prime }=ϵ$ and $v$ is the root. Let ${\alpha }^y$ be the next unprocessed run in $S$. We proceed as follows:

Step 1: Report Occurrences.

Query the truncate match reporting data structure with $(i_v,\alpha ,y)$ unless $i_v=-1$. For each pattern $j$ returned by the query, report that pattern $j$ occurs at location $|S^{\prime }|-|P_j|+x_j$.

Step 2: Follow Failure Links.

While $v$ is not the root and ${\alpha }^y\notin D_v$ set $v=F_v$. Finally, if ${\alpha }^y\in D_v$ let $v=D_v[{\alpha }^y]$.

At each node we visit when processing $S$, we use constant time to determine if we follow an edge or a failure link. We traverse one edge per run in $S$ and thus traverse at most $O(\overline{n})$ edges. Since a failure link points to a proper suffix, the total number of failure links we traverse cannot exceed the number of characters we process throughout the algorithm. Since we process $n$ characters we traverse at most $O(n)$ failure links. Furthermore, we report from at most one node per run in $S$, and by Lemma 7 we use $O(\overline{n}\log \log k+occ)$ time to report the locations of the matched patterns. In total, we use $O(n+\overline{n}\log \log k+occ)$ time.

By induction on the iteration $t$, we will show that $s_v$ is the longest suffix of $S^{\prime }$ in $T_{\text{RLE}}$ and that we report all starting positions of occurrences of patterns $𝒫$ in $S^{\prime }$. Initially, $t=0$, $S^{\prime }=ϵ$, and $v$ is the root of $T_{\text{RLE}}$ and thus $s_v=ϵ$.

For the induction step assume that at the beginning of iteration $t$, $s_v$ is the longest suffix of $S^{\prime }$ in $T_{\text{RLE}}$. Let ${\alpha }^y$ be the next unprocessed run in $S$ and let $X\subseteq 𝒫$ be the subset of patterns that has an occurrence that ends in the unprocessed run ${\alpha }^y$. Note that any pattern $P\in X$ has one occurrence that ends in the unprocessed run ${\alpha }^y$ since $P$ consists of at least two runs.

We first argue that we correctly report all occurrences. It follows immediately from the definition of truncate match that $X$ consists of all the patterns $P\in 𝒫$ that truncate matches $S^{\prime }{\alpha }^y$. Let $P_i^{\prime }$ be the longest suffix of $S^{\prime }$ among all the truncated patterns. We will show that $P\in X$ iff $P$ truncate matches $P_i^{\prime }{\alpha }^y$. Since $P_i^{\prime }$ is a suffix of $S^{\prime }$ it follows immediately that all patterns that truncate matches $P_i^{\prime }{\alpha }^y$ also truncate matches $S^{\prime }{\alpha }^y$. We will show by contradiction that $P\in X$ implies that $P$ truncate matches $P_i^{\prime }{\alpha }^y$. Assume that $P=P^{\prime }{\alpha }^x\in X$ but does not truncate match $P_i^{\prime }{\alpha }^y$. Since $P$ truncate matches $S^{\prime }{\alpha }^y$ we have that $x\le y$ and $P^{\prime }$ is a suffix of $S^{\prime }$. Thus if $P^{\prime }{\alpha }^x$ does not truncate match $P_i^{\prime }{\alpha }^y$ it must be the case that $P^{\prime }$ is not a suffix of $P_i^{\prime }$. But then $P^{\prime }$ is a longer suffix of $S^{\prime }$ than $P_i^{\prime }$ contradicting that $P_i^{\prime }$ is the longest suffix of $S^{\prime }$ among all truncated patterns. Thus the patterns that truncate match $P_i^{\prime }{\alpha }^y$ is exactly $X$ and by querying the truncate match reporting data structure with $(i,\alpha ,y)$, we report all occurrences in $X$ and hence the occurrences which end in the unprocessed run.

Finally, we will show that after step 2 the string $s_v$ is the longest suffix of $S^{\prime }{\alpha }^y$. Let $w$ be the node set to $v$ by the end of step 2, i.e., after iteration $t$ of the algorithm $v=w$. Assume for the sake of contradiction that after step 2, $s_w$ is not the longest suffix of $S^{\prime }{\alpha }^y$. Then either $s_w$ is not a suffix of $S^{\prime }{\alpha }^y$ or there is another node $u$ such that $s_u$ is a suffix of $S^{\prime }{\alpha }^y$ and $s_w$ is a proper suffix of $s_u$. By the definition of the failure links and the dictionary $D_v$ after step 2 $s_w$ must be a suffix of $S^{\prime }{\alpha }^y$. Furthermore, either $s_w=ϵ$ ($w$ is the root) or ${\alpha }^y\in D_{p(w)}$, where $p(w)$ is the parent of $w$. Assume that there is a node $u$ such that $s_u$ is a suffix of $S^{\prime }{\alpha }^y$ and $s_w$ is a proper suffix of $s_u$. Then there exist nodes $v^{\prime }$ and $u^{\prime }$ such that $s_w=s_{w^{\prime }}{\alpha }^y$ and $s_u=s_{u^{\prime }}{\alpha }^y$ and ${\alpha }^y\in D_{w^{\prime }}\cap D_{u^{\prime }}$. Since $s_w$ is a suffix of $s_u$ then $s_{w^{\prime }}$ is a suffix of $s_{u^{\prime }}$. At the beginning of step 2 $s_{u^{\prime }}$ must be a suffix of $s_v$ since by the induction hypothesis $s_v$ is the longest suffix of $S^{\prime }$. Since $u^{\prime }$ is longer than $w^{\prime }$ we meet $u^{\prime }$ before $w^{\prime }$ in the traversal in step 2. Since ${\alpha }^y\in D_{u^{\prime }}$ we would have stopped at node $u^{\prime }$ and not $w^{\prime }$.

First we construct the run-length encoded trie $T_{\text{RLE}}$ and the truncate match reporting data structure. In order to compute the failure link $F_u$ for a non-root node $u$ observe that if the edge $(v,u)$ is labeled ${\alpha }^x$, then there are 3 scenarios which determine the value of $F_u$.

• $\mathrm{■}$

  Either $F_u=D_w[{\alpha }^x]$ where $w$ is the first node such that ${\alpha }^x\in D_w$ which is reached by repeatedly following the failure links starting at node $F_v$.

• $\mathrm{■}$

  If no such node exists then if the root $r$ has an outgoing edge ${\alpha }^y$ where then $F_u=D_r[{\alpha }^{y^{\prime }}]$ where $y^{\prime }$ is maximum integer such that there is an outgoing edge ${\alpha }^{y^{\prime }}$ from the root $r$.

• $\mathrm{■}$

  Otherwise $F_u=r$.

We compute the failure links by traversing the trie in a Breadth-first traversal starting at the root using the above cases. Note that the second case requires a predecessor query. In our preprocessing of the $i_v$ values we use the reverse failure links $F_v^{\prime }$ of node $v\in T_{\text{RLE}}$, i.e., $u\in F_v^{\prime }$ if $F_u=v$. We compute these while computing the failure links. To compute $i_v$, we first set $i_v$ for each node $v$ which has a child $u$ corresponding to a pattern. We then start a Breadth-first traversal of the graph induced by the reverse failure links from each of these nodes. For each node $v$ we visit, we set $i_v=i_u$ for the parent $u$ of $v$ in the traversal. Note that each node is visited in exactly one of these traversals, since a node has exactly one failure link. For the remaining unvisited nodes let $i_v=-1$.

We can construct the run-length encoded trie of the patterns $𝒫$ in expected $O(\overline{m}+k\log \log k)$ time by Corollary 4 and the proof of Lemma 3. We use expected $O(\overline{m})$ time to construct the dictionaries $D_v$ of the nodes $v$ in the run-length encoded trie $T_{\text{RLE}}$ and $O(\overline{m}+k\log \log k)$ for the truncate match reporting data structure by Lemma 7. Since a failure link points to a proper suffix, each root-to-leaf path in $T_{\text{RLE}}$ can traverse a number of failure links proportional to the number of characters on the path. The sum of characters of all root-to-leaf paths is $O(m)$; hence, we traverse at most $O(m)$ failure links as we construct the failure links. We use at most one predecessor query for each node in $T_{\text{RLE}}$ as we construct the failure links and thus we use $O(\overline{m}\log \log m+m)$ time to construct the failure links by Lemma 2. Finally, computing $i_v$ requires $O(\overline{m})$ time to traverse $T_{\text{RLE}}$. In total, we use $O(\overline{m}\log \log m+m+k\log \log k)=O(\overline{m}\log \log m+m)$ in expectation.

To correctly report the occurrences of the single run patterns, we construct a dictionary $D$ such that $D[\alpha ]$ is the list of single run patterns of the character $\alpha$ sorted by their length. Let $S^{\prime }$ be the processed part of $S$ and let ${\alpha }^y$ be the next unprocessed run in $S$. To report the single run patterns occurring in the run ${\alpha }^y$ we do a linear scan of $D[\alpha ]$. For each single run pattern ${\alpha }^x$ in $D[\alpha ]$ the pattern ${\alpha }^x$ occurs in all the locations $|S^{\prime }|+i$ for $0\le i\le y-x$. If $x>y$ then ${\alpha }^x$ does not occur in ${\alpha }^y$ and neither does any pattern later in the list $D[\alpha ]$ since they are sorted by length. We can identify the single run patterns and construct $D$ in $O(\overline{m}+k\log \log k)$ expected time and reporting the occurrences of the single run patterns takes $O(1+\text{occ})$ time, neither of which impact our algorithm.

In summary, we have shown the following:

In the next section, we show how to improve the time bound to $O((\overline{m}+\overline{n})\log \log m+\text{occ})$ expected time, thus effectively removing the linear dependency on the uncompressed lengths of the string and the patterns.

We build the same structure as in Section 5, with a slight alteration to the failure links. Let $v$ be a node in the trie $T_{\text{RLE}}$ and let $\beta$ be the first character in $s_v$, i.e., $s_v={\beta }^{x}X$ for some $x$. The failure link $F_v$ stores a pointer to the node $u$ in $T_{\text{RLE}}$ such that $s_u$ is the longest suffix of $X$. Additionally, we store the length $x$ of the first run of $s_v$ as $Z_v=x$. We define the failure link for the root to be the root itself.

We partition the nodes of $T_{\text{RLE}}$ into groups as follows: Let $v$ and $u$ be two nodes of $T_{\text{RLE}}$. If $s_v={\beta }^{x}X$ and $s_u={\beta }^{y}X$, then $v$ and $u$ belong to the same group $G$. We define the group of the root to consist only of the root node. See Figure 4. For a group $G$ let $G_{\alpha ,x}$ be all the vertices $v\in G$ where $v$ has an outgoing edge labeled ${\alpha }^x$.

For each group $G$, we store the following:

• $\mathrm{■}$

  $D_G$: A dictionary of the labels of the outgoing edges of the nodes in $G$. For each label ${\alpha }^x$, $D_G[{\alpha }^x]$ is a predecessor structure of the nodes $v\in G_{\alpha ,x}$ ordered by the length of their first run $Z_v$.

The dictionaries use linear space with the number of outgoing edges of $G$. Since the number of edges and nodes in $T_{\text{RLE}}$ is $O(\overline{m})$ and the groups partition the nodes of $T_{\text{RLE}}$, then the combined size of the dictionaries of the groups is $O(\overline{m})$. In total, we use $O(\overline{m})$ space.

Given a run-length encoded string $S$ we report all locations of occurrences of the patterns $𝒫$ in $S$ as follows. We process $S$ one run at a time. Let $S^{\prime }$ be the processed part of $S$. We maintain the node $v$ in $T_{\text{RLE}}$ such that $s_v$ is the longest suffix of $S^{\prime }$. Initially, $S^{\prime }=ϵ$ and $v$ is the root. Let ${\alpha }^y$ be the next unprocessed run in $S$, and let $G$ denote the group of $v$.

Step 1: Report Occurrences.

Query the truncate match reporting data structure with $(i_v,\alpha ,y)$ unless $i_v=-1$. For each pattern $j$ returned by the structure, report that pattern $j$ occurs at location $|S^{\prime }|-|P_j|+x_j$.

Step 2: Follow Failure Links.

While $v$ is not the root and $Z_v$ does not have a predecessor in $D_G[{\alpha }^y]$ set $v=F_v$. Finally, if $D_G[{\alpha }^y]$ has a predecessor $u$ to $Z_v$ then $v=D_u[{\alpha }^y]$.

At each node we visit when processing $S$, we use $O(\log \log m)$ time to determine if we traverse an edge in the group or a failure link by Lemma 2. We traverse one edge per run in $S$ and thus traverse at most $O(\overline{n})$ edges. Since the suffix a failure link points to has fewer runs and the number of runs in $S$ is $\overline{n}$, then we traverse at most $O(\overline{n})$ failure links. Furthermore, we report from at most one node per run in $S$, and by Lemma 7 we use $O(\overline{n}\log \log k+occ)$ time to report the locations of the matched patterns. In total, we use $O(\overline{n}\log \log m+occ)$ time.

By induction on the iteration $t$, we will show that $s_v$ is the longest suffix of $S^{\prime }$ in $T_{\text{RLE}}$ and that we report all starting positions of occurrences of the patterns $𝒫$ in $S^{\prime }$. Initially, $t=0$, $S^{\prime }=ϵ$, and $v$ is the root of $T_{\text{RLE}}$ and thus $s_v=ϵ$. Assume that at the beginning of iteration $t$, $s_v$ is the longest suffix of $S^{\prime }$ in $T_{\text{RLE}}$. Let ${\alpha }^y$ be the next unprocessed run in $S$. By the same argument as in Section 5, we report all the occurrences of the patterns that end in the unprocessed run ${\alpha }^y$. What remains is to show that after step 2 the string $s_v$ is the longest suffix of $S^{\prime }{\alpha }^y$. Let $w$ be the node we set to $v$ in the end of step 2, i.e., after iteration $t$ of the algorithm $v=w$. Assume for the sake of contradiction that after step 2, $s_w$ is not the longest suffix of $S^{\prime }{\alpha }^y$. Then either $s_w$ is not a suffix of $S^{\prime }{\alpha }^y$ or there is another node $u$ such that $s_u$ is a suffix of $S^{\prime }{\alpha }^y$ and $s_w$ is a proper suffix of $s_u$. By the definition of the failure links and the dictionary $D_G$ after step 2 $s_w$ must be a suffix of $S^{\prime }{\alpha }^y$. Furthermore, either $s_w=ϵ$ ($w$ is the root) or ${\alpha }^y\in D_{p(w)}$, where $p(w)$ is the parent of $w$. Assume that there is a node $u$ such that $s_u$ is the longest suffix of $S^{\prime }{\alpha }^y$ and $s_w$ is a proper suffix of $s_u$. Then there is a node $u^{\prime }$ such that $s_u=s_{u^{\prime }}{\alpha }^y$ and ${\alpha }^y\in D_{u^{\prime }}$. At the beginning of step 2, $s_{u^{\prime }}$ must be a suffix of $s_v$ since by the induction hypothesis $s_v$ is the longest suffix of $S^{\prime }$. Hence in step 2 we would have stopped at a node $v^{\prime }$ in the group $G^{\prime }$ of node $u^{\prime }$. Furthermore, $Z_{v^{\prime }}\ge Z_{u^{\prime }}$ since $s_{u^{\prime }}$ is a suffix of $s_{v^{\prime }}$. Since ${\alpha }^y\in D_{u^{\prime }}$ then ${\alpha }^y\in D_{G^{\prime }}$ and in the predecessor structure $D_{G^{\prime }}[{\alpha }^y]$ the node $u^{\prime }$ will have $Z_{u^{\prime }}$ as a key and since $Z_{v^{\prime }}\ge Z_{u^{\prime }}$ and $s_u$ is the longest suffix of $S^{\prime }{\alpha }^y$ then $u^{\prime }$ will be the predecessor of $Z_{v^{\prime }}$ and thus after step 2 $w=D_{u^{\prime }}[{\alpha }^y]=u$.

First we construct the run-length encoded trie $T_{\text{RLE}}$ and the truncate match reporting data structure. We then compute the groups of $T_{\text{RLE}}$ as follows. First we group the children of the root $r$ based on the label on the outgoing edge, such that all children $v$ of $r$ with an $\alpha$ on the edge $(r,v)$ are in the same group. We compute the groups of all descendent nodes as follows. Given a group $G$ all the nodes in $D_G[{\alpha }^x]$ constitute a new group $G^{\prime }$ for ${\alpha }^x\in D_G$. We then compute failure links between groups. Note that since a failure link points to a suffix with at least one less run, all the nodes $v$ in a group $G$ will have the same failure link. We compute the failure link $F_u$ for a non-root node $u$ as follows. Let the label of edge $(v,u)$ be ${\alpha }^x$. There are 3 scenarios which determine the value of $F_u$.

• $\mathrm{■}$

  Either $F_u=D_w[{\alpha }^x]$ where $w$ is the first non-root node such that ${\alpha }^x\in D_w$ which is reached by repeatedly following the failure links starting at node $F_v$.

• $\mathrm{■}$

  if no such node exists and $u$ is not a child of the root $r$ and the root $r$ has an outgoing edge ${\alpha }^y$ where $y\le x$ then $F_u=D_r[{\alpha }^{y^{\prime }}]$ where $y^{\prime }$ is the maximum integer $y^{\prime }\le x$ such that there is an outgoing edge ${\alpha }^{y^{\prime }}$ from the root $r$.

• $\mathrm{■}$

  Otherwise $F_u=r$.

We compute the failure links by traversing the trie in a breadth-first traversal starting at the root using the above cases. Note that the second case requires a predecessor query. To compute $i_v$ we will simulate the reverse failure links used in Section 5. Observe that the failure links of Section 5 are composed of failure links where both endpoints are in the same group and failure links where the endpoints are in different groups. Since a failure link points to a suffix with at least one less run, we have only computed the failure links between groups. To simulate the failure links within a group observe that if $v,u\in G$ and $s_v={\beta }^x$ and $s_u={\beta }^y$ there is a failure link going from $v$ to $u$ in the data structure of Section 5 iff and there is no node $w\in G$ where $s_w={\beta }^z$ and . Hence by building a predecessor structure of the nodes in $G$ we can simulate the failure links of Section 5 and compute $i_v$.

We can construct the run-length encoded trie of the patterns $𝒫$ in expected $O(\overline{m}+k\log \log k)$ time by Corollary 4 and the proof of Lemma 3. We use expected $O(\overline{m})$ time to construct the dictionaries $D_v$ of the nodes $v$ in the run-length encoded trie $T_{\text{RLE}}$ and $O(\overline{m}+k\log \log k)$ for the truncate match reporting data structure by Lemma 7. To partition $T_{\text{RLE}}$ into groups we use $O(\overline{m})$ time, and $O(\overline{m}\log \log m)$ to construct the predecessor structures of the groups by Lemma 2. Since a failure link points to a suffix with at least one less run, each root-to-leaf path in $T_{\text{RLE}}$ can traverse a number of failure links proportional to the number of runs on the path. The sum of runs of all root-to-leaf paths is $O(\overline{m})$; hence, we traverse at most $O(\overline{m})$ failure links as we construct the failure links. We use at most one predecessor query for each node in $T_{\text{RLE}}$ as we construct the failure links and thus we use $O(\overline{m}\log \log m)$ time to construct the failure links by Lemma 2. Finally, computing $i_v$ requires $O(\overline{m}\log \log m)$ time to traverse $T_{\text{RLE}}$ and simulate the failure links. In total, we use $O(\overline{m}\log \log m+k\log \log k)=O(\overline{m}\log \log m)$ expected time. In summary, we have shown Theorem 1.