Near-Real-Time Solutions for Online String Problems

Strings are a fundamental data type in computer science, and many classical problems on strings have been studied extensively in the literature. An important class of those problems concerns online processing of large strings when the string is read letter by letter from left to right, while maintaining the desired information about the string read so far. This type of solution is often required in practice. Unfortunately, most online algorithms for strings provide only amortized time guarantees per letter, i.e., the average time spent to process each letter is bounded by a function of the input size, but some read letters may take much longer to process. This can be problematic in real-time applications, where it is important to have predictable processing times for each letter. In this paper, we focus on online algorithms with worst-case time guarantees per letter. While literature gives real-time algorithms for LZ78-like factorizations [43] with a static dictionary [18] for constant alphabets, palindrome recognition and pattern matching [15], for many classical problems on strings, online algorithms with efficient worst-case time guarantees per letter are not known.

In fact, a majority of string problems can be only solved efficiently if we maintain a full-text indexing data structure of the string read so far. One of the most fundamental such data structures is the suffix tree [39]. The first online construction of the suffix tree is due to Ukkonen [38], which builds a suffix tree online in time $O(n)$ for a constant-sized alphabet. However Ukkonen’s algorithm does not provide any worst-case time guarantee on processing an individual letter, other than a trivial $O(n)$ bound. For certain inputs, this bound is actually tight: Given a string $SSc$ of length $n$, Ukkonen’s algorithm maintains an active node of string depth at least $|S|$ after having parsed the prefix $SS$, but then needs to add branches for all suffixes of $S$ in case $c$ is a new letter, and thus creates $\mathrm{\Theta }(n)$ nodes just for updating the suffix tree for the last letter. (Spending $\mathrm{\Theta }(n)$ for the last letter may be a common phenomenon in practice since we usually append a unique delimiter letter $\$$ at the end of the input string.) To achieve worst-case time guarantees, a line of research is based on the idea to maintain a suffix tree (or similar data structure) for the inverted input string. The rationale for this is that appending a new letter to the input string amounts to introducing only one new suffix in the inverted string, which causes less updates to the data structure compared to Ukkonen’s algorithm. The starting point of this line of research is Weiner’s algorithm [39], historically the first linear-time algorithm for suffix tree construction for constant-sized alphabets. Weiner’s algorithm processes the string right-to-left by introducing a new suffix at each step, and is therefore suitable for this task. In its original version, Weiner’s algorithm does not provide a worst-case time guarantee on processing a single letter. However, in the following Section 2.1, we summarize modifications that accomplish this. These modifications result in double logarithmic worst-case times per letter, a time complexity referred to as near-real-time [6].

We assume the word RAM with word size $w\ge \log n$ bits, where $n$ is the length of the input string. Let $\mathrm{\Sigma }$ denote an integer alphabet of size $\sigma =|\mathrm{\Sigma }|=n^{O(1)}$. An element of ${\mathrm{\Sigma }}^{\ast }$ is called a string. Given a string $S\in {\mathrm{\Sigma }}^{\ast }$, we denote its length with $|S|$, its $i$-th letter with $S[i]$ for $i\in [1..|S|]$. Further, we write $S[i..j]=S[i]\mathrm{\cdots }S[j]$. We write $\overleftarrow{S}$ to denote the inverted string of $S$, i.e., $\overleftarrow{S}=S[|S|]S[|S|-1]\mathrm{\cdots }S[1]$. The suffix tree $\mathrm{𝖲𝖳}(S)$ of a string $S$ is a compacted trie representing all suffixes of $S$.

In what follows, we fix a string $T[1..n]$ over $\mathrm{\Sigma }$ as the input string to be processed online. Here, online means that the algorithm reads $T$ letter by letter and maintains the result for the processed portion of the string. All presented algorithms in this paper use $O(n)$ words of space, unless otherwise stated. Note that this means that the space is proportional to the size of the currently processed string (as opposed to the size of the entire string).

From now on, we will be considering the online setting where the input string $T$ is provided letter by letter from left to right, and we will be maintaining a suffix tree of the inverted string $\overleftarrow{T}$, using a variant of Weiner’s algorithm. Thus, a suffix of a current string will become an inverted prefix of the actually indexed string, etc. In our presentation, we will consider both the string and its inverted image and alternate between the two depending on the context which should be clear to the reader.

The longest repeating suffix array (LRS) of a string $T[1..n]$ is an array $\mathrm{𝖫𝖱𝖲}[1..n]$ such that for each position $i\in [1..n]$, $\mathrm{𝖫𝖱𝖲}[i]$ is the length of the longest suffix of $T[1..i]$ that occurs at least twice in $T[1..i]$. In other words, $\mathrm{𝖫𝖱𝖲}[i]$ is the length of the longest suffix of $T[1..i]$ occurring also in $T[1..i-1]$.

Okanohara and Sadakane [28] were the first to study computing this array online, for which they obtained $O({\log }^{3}n)$ worst-case time per letter. Prezza and Rosone [31] obtained $O({\log }^{2}n)$ amortized time, with $O(n\lg n)$ worst-case delay per letter. Importantly, both approaches [28] and [31] solve the problem under additional constraints on the space used by the algorithm: compact space for the former and zero-entropy compressed space for the latter.

We here show that, without the compact space constraint, we can efficiently compute $\mathrm{𝖫𝖱𝖲}$ in near-real-time as a by-product of maintaining $\mathrm{𝖲𝖳}$. Observe that under Weiner’s approach described in Section 2.1, the problem becomes the following.

We solve LongestRepeatingPrefix by revisiting the methodology of Amir et al. [2]. They reduce the problem to InsertionPoint, since the string label of the insertion point is the longest prefix of $T[i..]$ that already appears in $T[i+1..]$. Thus, updating $\mathrm{𝖲𝖳}(\overleftarrow{T})$ using Weiner’s algorithm allows us to compute $\mathrm{𝖫𝖱𝖲}$. When processing letter $T[i]$, we query LongestRepeatingPrefix on $\mathrm{𝖲𝖳}(\overleftarrow{T[1..i-1]})$ with letter $T[i]$. The answer is $\mathrm{𝖫𝖱𝖲}[i]$.

The longest previous factor array (LPF) of a string $T[1..n]$ is an array $\mathrm{𝖫𝖯𝖥}[1..n]$ such that for each position $i\in [1..n]$, $\mathrm{𝖫𝖯𝖥}[i]$ is the length of the longest prefix of $T[i..n]$ that has another occurrence starting at a position .

We first describe how to convert $\mathrm{𝖫𝖱𝖲}$ to $\mathrm{𝖫𝖯𝖥}$ and vice versa in linear time offline. A similar conversion between border and prefix arrays has been studied in the literature [4]. For that, we observe that we can restate the definitions of $\mathrm{𝖫𝖱𝖲}$ and $\mathrm{𝖫𝖯𝖥}$ as follows: Let $X_i=\{j\le i\mid j+\mathrm{𝖫𝖯𝖥}[j]-1\ge i\}$ be the set of positions $j$ such that the longest previous factor starting at $j$ covers position $i$. If $X_i\ne \mathrm{\varnothing }$, $|X_i|=i-\min (X_i)+1$. Consequently,

The problem of computing $\mathrm{𝖫𝖱𝖲}$ from $\mathrm{𝖫𝖯𝖥}$ is then reduced to finding the minimum in $X_i$ for each $i$. For that, we focus on irreducible LPF values, i.e., positions $i$ such that $\mathrm{𝖫𝖯𝖥}[i]>\mathrm{𝖫𝖯𝖥}[i-1]-1$. The important invariant is that irreducible LPF intervals of the form $[i..i+\mathrm{𝖫𝖯𝖥}[i]-1]$ cannot nest but overlap or are disjoint. Thus, we can determine $\mathrm{𝖫𝖱𝖲}[i]$ by maintaining the leftmost irreducible LPF interval covering position $i$. To this end, we scan the irreducible LPF values from left to right. More precisely, with a sweep-line $i\in [1..n]$ from left to right we maintain the leftmost irreducible LPF interval $[j..j+\mathrm{𝖫𝖯𝖥}[j]-1]$ such that $i\in [j..j+\mathrm{𝖫𝖯𝖥}[j]-1]$. Then $j$ is the minimum $j$ in $X_i$.

We can also compute $\mathrm{𝖫𝖯𝖥}$ from $\mathrm{𝖫𝖱𝖲}$ in linear time by scanning the $\mathrm{𝖫𝖱𝖲}$ array left-to-right and computing $\mathrm{𝖫𝖯𝖥}$ using the following rule. For each $i$ such that $\mathrm{𝖫𝖱𝖲}[i]\le \mathrm{𝖫𝖱𝖲}[i-1]$, we set $\mathrm{𝖫𝖯𝖥}[j]=i-j$ for all $j\in [i-\mathrm{𝖫𝖱𝖲}[i-1]..i-\mathrm{𝖫𝖱𝖲}[i]]$. For $i=n$, we complete the computation by setting $\mathrm{𝖫𝖯𝖥}[j]=n-j+1$ for all $j\in [n-\mathrm{𝖫𝖱𝖲}[n]+1..n]$.

Like the LCP array [32], the LPF array can be recovered from the list of its $r$ irreducible values in linear time [3], where it has been shown how to store the irreducible values in $2n+o(n)$ bits of space and still support constant-time access to either the $i$-th irreducible value or $\mathrm{𝖫𝖯𝖥}[i]$, for any given $i$. By an analogous argument, we can store the irreducible values of $\mathrm{𝖫𝖱𝖲}$ within the same space bound with the same query functionality [31]. It is therefore natural to ask whether the above conversions can be done on the irreducible values only. Actually, we can observe that the above algorithm for converting between $\mathrm{𝖫𝖱𝖲}$ and $\mathrm{𝖫𝖯𝖥}$ can be adapted to work on the irreducible values only, by skipping the assignments for reducible values.

The left-to-right conversion of $\mathrm{𝖫𝖱𝖲}$ into $\mathrm{𝖫𝖯𝖥}$ can also be used to compute the $\mathrm{𝖫𝖯𝖥}$ values online by computing $\mathrm{𝖫𝖱𝖲}$ values online as described in Section 3, with a delay. By delay we mean that given $T[1..i]$ is the currently processed text, then we have not yet computed the $\mathrm{𝖫𝖯𝖥}[j]$ last values for the positions $j\in [i-\mathrm{𝖫𝖱𝖲}[i]+1..i]$. To turn our offline left-to-right conversion into (near-)real-time, we need to deamortize the sequence of assignments triggered by . This can be done by distributing these assignments over multiple rounds and setting a constant number of values at each round, similarly to Steps 4 and 5 of Breslauer–Italiano algorithm (Section 2.1). The delayed assignments can be stored in a FIFO data structure. By induction we observe that the maximal number of delayed assignments is bounded by ${\max }_i\mathrm{𝖫𝖱𝖲}[i]$. We thus obtain the following result.

The LZ77 factorization of a string $T$ is defined as follows: a factorization $T=F_1\mathrm{\cdots }{F}_z$ it is the LZ77 factorization of $T$ if each next factor $F_x$, for $x\in [1..z]$, is either the first occurrence of a letter or the longest prefix of $F_x\mathrm{\cdots }{F}_z$ that occurs at least twice in $F_1\mathrm{\cdots }{F}_x$. The factorization can be written like a macro scheme [35], i.e., by a list storing either plain letters or pairs of referred positions and lengths, where a referred position is a previous text position from where the letters of the respective factor can be copied.

While practical compressors based the LZ77 [42] factorization such as gzip and 7zip work with a sliding window over the input text, the original LZ77 factorization considers the entire text as the search buffer. For the online setting, Gusfield’s textbook [17, APL 16] presents an algorithm that runs in $O(\log \sigma )$ amortized time per letter. The main idea is to maintain the suffix tree of the text read so far using Ukkonen’s algorithm [38], and simultaneously compute each next factor by a top-down traversal of the tree. Since we can easily extract the LZ77 factorization from the $\mathrm{𝖫𝖱𝖲}$ or $\mathrm{𝖫𝖯𝖥}$ arrays, algorithms of Sections 3,4 can be also used to compute it. Direct online algorithms for computing the LZ77 factorization have also been proposed, additionally focusing on space saving. In this line of research, Starikovskaya [34] proposed an algorithm in $O({\log }^{2}n)$ amortized time per letter by returning to Ukknonen’s suffix tree construction algorithm. Subsequently, Yamamoto et al. [41] obtained $O(\log n)$ amortized time per letter by constructing the directed acyclic word graph [5], and finally Policriti and Prezza [29] achieved the same time bounds with a dynamic FM-index in zero-order entropy compressed space.

Here we diverge from this line of research by allowing $O(n)$ words of space but focusing on the worst-case time per letter. Using the near-real-time computation of $\mathrm{𝖫𝖱𝖲}$ (Section 3), it is straightforward to compute the LZ77 factorization within the same time bounds.

Online computation of LZ77 factorization amounts to reporting if the current position $i$ extends the current factor or starts a new one. In the latter case, the previous factor ends at position $i-1$ and $i$ is the first position of a new factor. We can determine this by comparing $i-\mathrm{𝖫𝖱𝖲}[i]$ with the beginning $s_x$ of the current factor $F_x$. If $i-\mathrm{𝖫𝖱𝖲}[i]+1\le s_x$, then $i$ extends $F_x$, otherwise $F_x$ ends at $i-1$ and $i$ starts a new factor $F_{x+1}$. We observe that $\mathrm{𝖫𝖱𝖲}[i]=0$ if and only if $T[i]$ is the leftmost occurrence of a letter.

Given a substring $S$ of a text $T[1..n]$, let $\mathrm{\#}{\mathrm{𝑜𝑐𝑐}}_T(S)$ denote the number of occurrences of $S$ in $T$. A substring $S$ of $T$ is called unique in $T$ if $\mathrm{\#}{\mathrm{𝑜𝑐𝑐}}_T(S)=1$ and repeating in $T$ if $\mathrm{\#}{\mathrm{𝑜𝑐𝑐}}_T(S)\ge 2$. A unique substring $S$ of $T$ is called a minimal unique substring of $T$ if $S$ is unique and any proper substring of $S$ is repeating in $T$. Since a unique substring $S$ of $T$ has exactly one occurrence in $T$, it can be identified with a unique interval $[\mathrm{\ell }..r]\subseteq [1..n]$ with $S=T[\mathrm{\ell }..r]$. We denote the set of intervals corresponding to the MUSs of $T$ by $\mathrm{𝖬𝖴𝖲}(T)=\{[s..t]\mid T[s..t]\text{is a MUS of}T\}$. By the definition of MUSs, $[s..t]\in \mathrm{𝖬𝖴𝖲}(T)$ if and only if (a) $T[s..t]$ is unique in $T$, (b) $T[s+1..t]$ is repeating in $T$, and (c) $T[s..t-1]$ is repeating in $T$.

Mieno et al. [24] present an algorithm for computing MUSs in a sliding window and, in particular, study how $\mathrm{𝖬𝖴𝖲}(T)$ can be updated when a new letter $T[j+1]$ is appended to $T[1..j]$. We summarize these updates here, slightly modifying the description of [24]. Denote $\mathrm{𝗅𝗋𝗌}[j]$ the longest repeating suffix of $T[1..j]$, i.e. $\mathrm{𝖫𝖱𝖲}[j]=|\mathrm{𝗅𝗋𝗌}[j]|$. Denote $\mathrm{𝗌𝖽𝗌}[j]$ the shortest suffix of $T[1..j]$ with exactly two occurrences in $T[1..j]$ (that is, having exactly one previous copy). Since $\mathrm{𝗅𝗋𝗌}[j]$ can admit the empty string, $\mathrm{𝗅𝗋𝗌}[j]$ always exists. On the other hand, $\mathrm{𝗌𝖽𝗌}[j]$ may not exist when no suffix of $T[1..j]$ occurs exactly twice, i.e., $\mathrm{\#}{\mathrm{𝑜𝑐𝑐}}_{T[1..j]}(T[i..j])\ne 2$ for all $i\in [1..j]$.

The size of $\mathrm{𝗅𝗋𝗌}[j]$ and the ending position of the previous copy of $\mathrm{𝗌𝖽𝗌}[j]$ (if $\mathrm{𝗌𝖽𝗌}[j]$ exists) are the two parameters we need to know in order to specify all possible modifications to $\mathrm{𝖬𝖴𝖲}(T[1..j])$ when $T[j+1]$ is appended to $T[1..j]$. These modifications can consist of one deletion of a MUS and up to three additions of new MUSs, specified below.

1. (1):

   If $\mathrm{𝖫𝖱𝖲}[j+1]\le \mathrm{𝖫𝖱𝖲}[j]$, then $[j+1-\mathrm{𝖫𝖱𝖲}[j+1]..j+1]$ is a new MUS to be added to $\mathrm{𝖬𝖴𝖲}(T[1..j+1])$.

   Proof.

   By definition of $\mathrm{𝗅𝗋𝗌}[j+1]$, on the one hand, $T[j+1-\mathrm{𝖫𝖱𝖲}[j+1]..j+1]$ is unique. On the other hand, both $T[j+1-\mathrm{𝖫𝖱𝖲}[j+1]..j]$ and $T[j+1-\mathrm{𝖫𝖱𝖲}[j+1]+1..j+1]$ are repeating in $T[1..j+1]$. The former is repeating as it must be a suffix of $T[j-\mathrm{𝖫𝖱𝖲}[j]+1..j]$. $◀$

2. (2):

   If $\mathrm{𝗌𝖽𝗌}[j+1]$ exists, let $T[s..q]$ be its previous copy (). Then $[s..q]$ is in $\mathrm{𝖬𝖴𝖲}(T[1..j])$ but not in $\mathrm{𝖬𝖴𝖲}(T[1..j+1])$ and therefore should be deleted.

   Proof.

   $T[s..q]$ was unique in $T[1..j]$ as it occurs exactly twice in $T[1..j+1]$. $T[s+1..q]$ must be repeating in $T[1..j]$ as $T[s..q]=\mathrm{𝗌𝖽𝗌}[j+1]$ is the shortest suffix of $T[1..j+1]$ occurring twice, therefore $T[s+1..q]$ must occur at least three times in $T[1..j+1]$ and therefore at least twice in $T[1..j]$. On the other hand, $T[s..q-1]$ is a repeating suffix of $T[1..j]$. Therefore, $T[s..q]$ was a MUS in $T[1..j]$ that is no longer a MUS in $T[1..j+1]$.

   Note that $T[s..q]$ may overlap $T[j+1-|\mathrm{𝗌𝖽𝗌}[j+1]|+1..j+1]$, in particular, it may happen that $q=j$. In this case, $T[s..j]=\mathrm{𝗌𝖽𝗌}[j+1]=T[s+1..j+1]$ and therefore $T[s..j+1]=T{[j+1]}^k$, $k=|\mathrm{𝗌𝖽𝗌}[j+1]|+1$, is the single letter run which is unique in $T[1..j+1]$. Observe that in this case, we have $\mathrm{𝗌𝖽𝗌}[j+1]=\mathrm{𝗅𝗋𝗌}[j+1]$. The situation is illustrated on the right of Figure 3. $◀$

   If $\mathrm{𝗌𝖽𝗌}[j+1]$ exists, one or two new MUSs can appear in this case, specified in the following and illustrated on the left in Figure 3.

3. (3):

   A new potential MUS to be added to $\mathrm{𝖬𝖴𝖲}(T[1..j+1])$ becomes $[s..q+1]$ provided that no (shorter) MUS in $T[1..j]$ ends at $q+1$.

   Proof.

   Since $T[s..q]=\mathrm{𝗌𝖽𝗌}[j+1]$ has a single non-suffix occurrence in $T[1..j+1]$, $T[s..q+1]$ is unique in $T[1..j+1]$. Since $T[s..q]$ is repeating in $T[1..j+1]$, the shortest unique suffix $T[\mathrm{\ell }..q+1]$ of $T[s..q+1]$ is a MUS in $T[1..j+1]$. If $\mathrm{\ell }=s$, this MUS is a new one, otherwise it already existed in $T[1..j]$. $◀$

4. (4):

   A new potential MUS to be added to $\mathrm{𝖬𝖴𝖲}(T[1..j+1])$ becomes $[\mathrm{\ell }-1..q]$ where $T[\mathrm{\ell }..q]=\mathrm{𝗅𝗋𝗌}[j+1]$, provided that $\mathrm{\ell }\ge 1$ and no (shorter) MUS in $T[1..j]$ starts at $\mathrm{\ell }-1$.

   Proof.

   By definition of $\mathrm{𝗅𝗋𝗌}[j+1]$, $T[\mathrm{\ell }-1..q]$ is unique in $T[1..j+1]$ and $T[\mathrm{\ell }..q]$ is repeating. Therefore, the shortest unique prefix $T[\mathrm{\ell }-1..p]$ of $T[\mathrm{\ell }-1..q]$ is a MUS in $T[1..j+1]$. If $p=q$, this MUS is a new one, otherwise it already existed in $T[1..j]$. $◀$

We now turn to the implementation of the above updates. First, we need to represent the current set of MUSs. Knowing that MUSs cannot nest, one can bijectively map the starting position of a MUS to its ending position, and vice versa. The authors of [24] used this insight to create two arrays to maintain MUSs via the bijection and its reverse. This allows them to retrieve a MUS by querying one of its end points, and adding/removing a MUS, all in constant time per operation.

To implement the updates online, the authors of [24] maintain $\mathrm{𝖲𝖳}(T[1..j])$ with Ukkonen’s suffix tree construction algorithm [38]. While reading a new letter $T[j+1]$ from the text, they update $\mathrm{𝖲𝖳}(T[1..j])$ and compute the locus of $\mathrm{𝗅𝗋𝗌}[j+1]$ and $\mathrm{𝗌𝖽𝗌}[j+1]$, which they call active points, and their string lengths $\mathrm{𝖫𝖱𝖲}[j+1]$ and $|\mathrm{𝗌𝖽𝗌}[j+1]|$ respectively. Computing $\mathrm{𝗅𝗋𝗌}[j+1]$ is a direct by-product of Ukkonen’s algorithm, whereas computing $\mathrm{𝗌𝖽𝗌}[j+1]$ requires some additional work. Using this information, the set of MUSs is updated using the above description.

We now show how to efficiently implement the updates when we maintain the suffix tree online with Weiner’s algorithm applied to the inverted text, as discussed in Section 2. Maintaining $\mathrm{𝗅𝗋𝗌}[i]$ has been studied in Section 3. To maintain $\mathrm{𝗌𝖽𝗌}[i]$, we need to solve the following problem.

Assume a new letter $T[j+1]$ is appended to $T[1..j]$. As explained in Section 3, the locus of $\mathrm{𝗅𝗋𝗌}[j+1]$ corresponds to the insertion point of Weiner’s algorithm (see Section 2.1). If the insertion point is an already existing node in $\mathrm{𝖲𝖳}(\overleftarrow{T[1..j]})$, then $\mathrm{𝗅𝗋𝗌}[j+1]$ occurs at least three times in $T[1..j+1]$ and $\mathrm{𝗌𝖽𝗌}[j+1]$ does not exist. Otherwise, the locus of $\mathrm{𝗅𝗋𝗌}[j+1]$ becomes a node in $\mathrm{𝖲𝖳}(\overleftarrow{T[1..j+1]})$ with exactly two children (one of them is a leaf). Therefore, in this case, $\mathrm{𝗌𝖽𝗌}[j+1]$ exists and its locus is located on the parent edge to the locus of $\mathrm{𝗅𝗋𝗌}[j+1]$ and thus is obtained “for free” in constant time, simplifying the algorithm of [24].

Once $\mathrm{𝗅𝗋𝗌}[j+1]$ and $\mathrm{𝗌𝖽𝗌}[j+1]$ are found, we update the set of MUSs implementing the modifications described above:

1. 1.

   Add a new MUS $[j+1-\mathrm{𝖫𝖱𝖲}[j+1]..j+1]$.

2. 2.

   If $\mathrm{𝗌𝖽𝗌}[j+1]$ exists, find its non-suffix occurrence $[s..q]$: $s$ is the label of the leaf of the locus of $\mathrm{𝗌𝖽𝗌}[j+1]$ that already existed in $\mathrm{𝖲𝖳}(T[1..j])$, and $q=s+|\mathrm{𝗌𝖽𝗌}[j+1]|-1$. Delete the MUS $[s..q]$.

3. 3.

   If there is no MUS ending at position $q+1$, add the MUS $[s..q+1]$.

4. 4.

   If $q-\mathrm{𝖫𝖱𝖲}[j+1]\ge 1$ and there is no MUS starting at position $q-\mathrm{𝖫𝖱𝖲}[j+1]$, add the MUS $[q-\mathrm{𝖫𝖱𝖲}[j+1]..q]$.

Following [24], we maintain two integer arrays $X_1$ and $X_2$ of size $n$ mapping starting positions of the MUSs to their ending positions, and vice versa. In our online setting, arrays $X_1$ and $X_2$ are dynamic and grow by one entry to the right at each newly read letter. We implement $X_1$ and $X_2$ using the standard doubling technique (e.g. [33, Section 3.2]) which allocates a new array fragment of size $n$ when the size of the current string reaches $n$, thus doubling the occupied memory. While this implementation maintains the $O(n)$ memory, the waisted memory is also up to $O(n)$. To reduce the waisted memory, one can use the resizeable array of Brodnik [7] which supports the growable array operations in $O(1)$ worst-case time while having only up to $O(\sqrt{n})$ of waisted memory. We summarize this section with the following final result.

The reversed LZ factorization was introduced by Kolpakov and Kucherov [19] as a helpful tool for detecting gapped palindromes, i.e., substrings of a given text $T$ of the form $\overleftarrow{S}GS$ for two strings $S$ and $G$. The reversed LZ factorization of $T$ is defined recursively as follows: a factorization $T=F_1\mathrm{\cdots }{F}_z$ is the reversed LZ factorization of $T$ if each factor $F_x$, for $x\in [1..z]$, is either the first occurrence of a letter or the longest prefix of $F_x\mathrm{\cdots }{F}_z$ that has an inverted copy $\overleftarrow{F_x}$ as a substring of $F_1\mathrm{\cdots }{F}_{x-1}$. Like LZ77, the factorization is a macro scheme [35]. Among all variants of such a left-to-right parsing using the reversed substring as a reference to the formerly parsed part of the text, the greedy parsing achieves optimality with respect to the number of factors [11, Theorem 3.1] since the reversed occurrence of $F_x$ can be the prefix of any suffix in $F_1\mathrm{\cdots }{F}_{x-1}$, and thus fulfills the suffix-closed property [11, Definition 2.2].

Kolpakov and Kucherov [19] also gave an algorithm computing the reversed LZ factorization in $O(n\lg \sigma )$ time using $O(n\lg n)$ bits of space, by applying Weiner’s suffix tree construction algorithm [39] on the reversed text $\overleftarrow{T}$. Later, Sugimoto et al. [36] presented an online factorization algorithm running in $O(n{\lg }^2\sigma )$ time using $O(n\lg \sigma )$ bits of space. Recently, Köppl [21] improved the time complexity to $O(n)$ while keeping the space usage of $O(n\lg \sigma )$ bits. While the last approach works offline, the former results are online algorithms with amortized time bounds per letter.

We studied applications of the Breslauer–Italiano deamoritization of Weiner’s algorithm to obtain near-real-time online algorithms for several string processing problems. The crucial observation was that the deamortization of the suffix tree maintenance algorithm does not interfere with the functionality of the suffix tree needed to solve these problems. We gave online algorithms computing the longest repeating suffixes, the Lempel–Ziv factorization, the set of minimal unique substrings, and the reversed Lempel–Ziv factorization (with and without self-references) in $O(n)$ space and $O(t_{\text{SU}})$ worst-case time per letter, where $t_{\text{SU}}$ depends on the implementation of the suffix tree construction algorithm but is at most $O({\log }^2\log n)$. We believe that this approach can be applied to obtain near-real-time online algorithms for other problems on strings, which will be the subject of our forthcoming work.