% Deterministic Sparse Suffix Sorting on Rewritable Texts
% Johannes Fischer
Tomohiro I
Dominik K\"{o
Given a rewriteable text $T$ of length $n$ on an alphabet of size $\sigma$, we propose an online algorithm that computes the sparse suffix array and the sparse longest common prefix array of $T$ in $\Oh{\abs{\Comlcp \sqrt{\lg n + m \lg m \lg n \lg^* n$ time by using the text space and $\Oh{m$ additional working space, where $m$ is the number of some positions $\Pos$ on $[1..n]$, provided online and arbitrarily, and $\Comlcp = \bigcup_{p,p' \in \Pos, p \neq p' [p..p+\lcp(T[p..], T[p'..])]$.
main.tex
%Standard:
\documentclass{article}
\newcommand{\institute}[1]{}
\usepackage[natbib,cref,pdf,theorems,draft]{nikis} 
%Springer:
%\let\oldvec\vec% Store \vec in \oldvec
%\documentclass{llncs}
%\let\vec\oldvec% Restore \vec from \oldvec
%\usepackage[natbib,cref,springer,pdf,draft]{nikis} 


%\usepackage[natbib,cref,theorems,draft]{nikis} 

\usepackage{ifthen}
\newboolean{withAlgo} %Deklaration
\setboolean{withAlgo}{false} %Zuweisung

\usepackage[utf8]{inputenc}




%\usepackage{amssymb,amsthm,amsmath}
\usepackage{amssymb,amsmath}
\usepackage{enumerate} % for \enumerate[a)]
\usepackage[shortlabels]{enumitem} %enum labels for \ref{}
\usepackage{booktabs} %toprule
\usepackage{graphicx} %includegraphics
\ifthenelse{\boolean{withAlgo}}{%
	\usepackage[linesnumbered,ruled,vlined]{algorithm2e}
	\SetKwProg{function}{Function}{}{}
}{}%withAlgo

\usepackage{comment}

\newcommand{\invalid}{\texttt{0}} % the "invalid name" to make all blocks of length 3

\newcommand{\Type}[1]{\texttt{type\,#1}}

\newcommand{\SSA}[1][]{\UnaryOperator[#1]{\instancename{SSA}}}
\newcommand{\SLCP}[1][]{\UnaryOperator[#1]{\instancename{SLCP}}}

\newcommand{\idsetsize}[1]{\abs{\idset}} %\varphi_{#1}}
\newcommand{\idset}{\mathcal{V}}
\newcommand{\dic}{\mathfrak{D}} %dictionary used for esp cfg
\newcommand{\Comlcp}{\mathcal{C}} % common lcp, \bigcup_{p,p' \in \Pos, p \neq p'} [p..p+\lcp(T[p..n], T[p'..n])]
\newcommand{\Maxlcp}{\ensuremath{\ell}} % largest lcp value
\newcommand{\lcontext}[1][]{\mathit{\Delta}_{\mathup{L}#1}}
\newcommand{\jcontext}[1][]{\mathit{\Delta}}
\newcommand{\rcontext}[1][]{\mathit{\Delta}_{\mathup{R}#1}}
\newcommand{\espnode}[1]{\langle #1 \rangle}
\newcommand{\maxlcp}{\mathit{maxlcp}}
\newcommand{\margin}{\ensuremath{f}}
\newcommand{\gap}{\ensuremath{g}}
\newcommand{\lookupTime}{t_{\mathup{\lambda}}}
\newcommand{\lookupTimeBest}{\lg n}
\newcommand{\lookupEta}{\lookupTime}
\newcommand{\lookupUpper}{\lookupTime}

\newcommand{\wlogg}{without loss of generality}
\newcommand{\Pos}{\mathcal{P}}
\newcommand{\Suf}{\mathit{Suf}}
\newcommand{\ibeg}[1]{\mathsf{b}(#1)}% beginning position of the interval #1
\newcommand{\iend}[1]{\mathsf{e}(#1)}% ending position of the interval #1
\newcommand{\SetStr}{\mathcal{S}}

\newcommand{\wordpack}{/ \lg_{\sigma}n} %{\lg \sigma / \lg n}
\newcommand{\numnames}{\abs{\idset}}

\newcommand{\intervalI}{\mathcal{I}} % use for intervals
\newcommand{\intervalJ}{\mathcal{J}} % use for intervals
\newcommand{\intervalK}{\mathcal{K}} % use for intervals


\newcommand{\lcontexttree}[1]{\lcontext[,#1]}
\newcommand{\rcontexttree}[1]{\rcontext[,#1]}

\newcommand{\SAVL}{\mathsf{SAVL}}
\newcommand{\SAVLT}{suffix AVL tree}

\newcommand{\eTree}{ET}
\newcommand{\hTree}{HT}
\newcommand{\teTree}{tET}
\newcommand{\thTree}{tHT}
\newcommand{\lce}[1][]{\UnaryOperator[#1]{\mathit{lce}}}
\newcommand{\lcp}[1][]{\UnaryOperator[#1]{\mathit{lcp}}}

\newcommand{\etInst}[1][]{\UnaryOperator[#1]{\instancename{\eTree}}}
\newcommand{\hInst}[1][]{\UnaryOperator[#1]{\instancename{\hTree}}}
\newcommand{\teInst}[1][]{\UnaryOperator[#1]{\instancename{\teTree}}}
\newcommand{\thInst}[1][]{\UnaryOperator[#1]{\instancename{\thTree}}}
\newcommand{\DynLCE}{dynLCE}
\newcommand{\DynLCEInst}[1][]{\UnaryOperator[#1]{\instancename{\DynLCE}}}

\newcommand{\esp}[1][]{\UnaryOperator[#1]{\functionname{esp}}}
%\newcommand{\hsp}[1][]{\UnaryOperator[#1]{\functionname{hsp}}}
\newcommand{\mlcp}[1]{\text{mlcp}_{#1}}
\newcommand{\mlcparg}[1]{\text{mlcparg}_{#1}}

\newcommand{\LCEI}{LCE interval}
\newcommand{\timeSuffix}{t_{\mathup{S}}}
\newcommand{\timeLCE}[1]{t_{\mathup{L}}(#1)}
\newcommand{\timeMerge}[1]{t_{\mathup{M}}(#1)}
\newcommand{\timeConstruct}[1]{t_{\mathup{C}}(#1)}
\newcommand{\memref}{\mathup{\tt ref}}
\newcommand{\memtext}{\mathup{\tt text}}

\newcommand{\numNodes}[1]{#1/2^\eta}
%\newcommand{\numNodes}[1]{\psi_{#1}}

\newcommand{\textS}{X}
\newcommand{\textT}{Y}
\newcommand{\textU}{Z}
\newcommand{\textV}{W}

% mathsf: instances and constructor names
% mathup: abbreviations
% tt: OOP-methods, pseudo-code functions
% mathit: function names

\title{%
  Deterministic Sparse Suffix Sorting on Rewritable Texts
}
\date{}
\author{%
  Johannes Fischer
  \and
  Tomohiro I
  \and
  Dominik K\"{o}ppl
}
\institute{%
  Department of Computer Science, TU Dortmund, Germany\\
  \email{(johannes.fischer, tomohiro.i)@cs.tu-dortmund.de,}
  \email{dominik.koeppl@tu-dortmund.de}
}


\begin{document}

\maketitle


%niki: We mixed 'string' and 'text'. I like to call the global large string T a text, while calling the small ones X,Y,Z a string.
\begin{abstract}
Given a rewriteable text $T$ of length $n$ on an alphabet of size $\sigma$,
we propose an online algorithm that computes the sparse suffix array and the sparse longest common prefix array of $T$
in
$\Oh{\abs{\Comlcp} \sqrt{\lg n} +  m \lg m \lg n \lg^* n}$ time by using the text space and $\Oh{m}$ additional working space, where $m$ is the number of some positions $\Pos$ on $[1..n]$, provided online and arbitrarily, 
and $\Comlcp = \bigcup_{p,p' \in \Pos, p \neq p'} [p..p+\lcp(T[p..], T[p'..])]$.
\end{abstract}

\section{Introduction}
Sorting suffixes of a long text lexicographically is an important first step for many text processing algorithms~\cite{puglisi07taxonomy}.
The complexity of the problem is quite well understood, as for integer alphabets
suffix sorting can be done in optimal linear time~\cite{ksb2006}, and also almost in-place~\cite{nong11two}.
In this article, we consider a variant of the problem:
instead of computing the order of \emph{every} suffix, we address the \intWort{sparse suffix sorting problem}.
Given a text $T[1..n]$ of length $n$ and a set $\Pos\subseteq [1..n]$ of~$m$ arbitrary positions in $T$,
the problem asks for the (lexicographic) order of the suffixes starting at the positions in $\Pos$.
The answer is encoded by a permutation of $\Pos$, which
is called the \intWort{sparse suffix array~(SSA)} of~$T$ (with respect to $\Pos$).

Like the ``full'' suffix arrays,
%why plural 'suffix arrays'? I think abouth SA (and SSA) as an abstract data type, with different implementations.
we can enhance \SSA[T,\Pos] by the length of the longest common prefix~(LCP) between adjacent suffixes in \SSA[T,\Pos],
which we call the \intWort{sparse longest common prefix array~(SLCP)}.
In combination, \SSA[T,\Pos] and \SLCP[T,\Pos] store the same information as the \intWort{sparse suffix tree}, i.e.,
they implicitly represent a compacted trie over all suffixes starting at the positions in $\Pos$.
This allows us to use the SSA as an efficient index for pattern matching, for example.
%niki: can you add a reference here?

Based on classic suffix array construction algorithms~\cite{ksb2006,nong11two}, 
sparse suffix sorting is easily conducted in $\Oh{n}$ time if $\Oh{n}$ additional working space is available.
For $m = \oh{n}$, however, the needed working space may be too large, compared to the final space requirement of~\SSA[T]\@.
Although some special choices of~$\Pos$ (e.g., evenly spaced suffixes or prefix codes) admit space-optimal $\Oh{m}$ construction algorithms~\cite{ferragina07suffix}, the problem of sorting arbitrary choices of suffixes in small space seems to be much harder. We are aware of the following results: As a deterministic algorithm, \citet{ksb2006}
gave a trade-off using $\Oh{\tau m +n\sqrt{\tau}}$ time and $\Oh{m+n/\sqrt{\tau}}$ working space 
with a parameter $\tau \in [1, \sqrt{n}]$.
If randomization is allowed, there is a technique based on Karp-Rabin fingerprints,
first proposed by \citet{BFGKSV13} and later improved by \citet{I2014FSS}.
The latest one works in $\Oh{n \lg n}$ expected time and $\Oh{m}$ additional space.

\subsection{Computational Model}
We assume that the text of length $n$ is loaded into RAM.
Our algorithms are allowed to overwrite parts of the text, as long as they can restore the text into its original form at termination. Apart from this space, we are only allowed to use $\Oh{m}$ additional words.
The positions in $\Pos$ are assumed to arrive on-line, implying in particular that they need not be sorted.
We aim at worst-case efficient \emph{deterministic} algorithms.

Our computational model is the word RAM model with word size $\Om{\lg n}$.
Here, characters use $\lceil\log\sigma\rceil$ bits and can hence be packed into $\log_\sigma n$ words, where $\sigma$ is the alphabet size. Comparing two strings $\textS$ and~$\textT$ takes
$\Oh{\lcp(\textS, \textT)\wordpack}$
time, where $\lcp(\textS, \textT)$ denotes the length of the longest common prefix of $\textS$ and $\textT$.

\subsection{Algorithm Outline and Our Results}

Our main algorithmic idea is to insert the suffixes starting at positions of $\Pos$ into a self-balancing binary search tree~\cite{Irving2003sbs}; since each insertion invokes $\Oh{\lg m}$ suffix-to-suffix comparisons, 
the time complexity is $\Oh{\timeSuffix m \lg m}$, where $\timeSuffix$ is the cost for each suffix-to-suffix comparison.
If all suffix-to-suffix comparisons are conducted by naively comparing the characters,
the resulting worst case time complexity is $\Oh{n m \lg m}$.
In order to speed this up,
our algorithm identifies large identical substrings at different positions
during different suffix-to-suffix comparisons.
Instead of performing naive comparisons on identical parts over and over again,
we build a data structure (stored in redundant text space) that will be used to accelerate 
subsequent suffix-to-suffix comparisons. 
Informally, when two (possibly overlapping) substrings in the text are detected to be the same, one substring can be overwritten.
%This type of redundancy correlates with the number and length of the LCP values of the suffixes in question.
%In other words, the worse the scenario becomes for the naive approach, 
%the more advantageous our approach seems to be.

With respect to the question of ``how'' to accelerate suffix-to-suffix comparisons,
we focus on a technique that is called \intWort{edit sensitive parsing~(ESP)}~\cite{Cormode2007sed}.
Its properties allow us to compute the \intWort{longest common extension~(LCE)} 
of any two substrings efficiently.
We propose a new variant of ESP, which we call \intWort{hierarchical stable parsing~(HSP)},
in order to build our data structure for LCE queries efficiently in text space.

We make the following definition that allows us to analyse the running time more accurately.
Define $\Comlcp := \bigcup_{p,p' \in \Pos, p \neq p'} [p..p+\lcp(T[p..], T[p'..])]$ as the set of positions that must be compared for distinguishing the suffixes from $\Pos$.
Then sparse suffix sorting is trivially lower bounded by $\Om{\abs{\Comlcp}\wordpack}$ time.

\begin{theorem}\label{thmSparseSuffixSorting}
	Given a text $T$ of length $n$ that is loaded into RAM,
  the SSA and SLCP of $T$ for a set of $m$ arbitrary positions can be computed deterministically in 
  $\Oh{\abs{\Comlcp} \sqrt{\lg n} +  m \lg m \lg n \lg^* n}$ time, using $\Oh{m}$ additional working space.
\end{theorem}

Note that the running time may actually be sublinear (excluding the loading cost for the text).
To the best of our knowledge, this is the first algorithm having the worst-case performance guarantee close to the lower bound.
All previously mentioned (deterministic and randomized) algorithms take $\Om{n}$ time even if we exclude the loading cost.
Also, general string sorters (e.g., forward radix sort~\cite{forwardradixsort} or three-way string quicksort~\cite{sedgewickAlgorithms}),
which do not take advantage of the suffix overlapping,
suffer from the lower bound of $\Om{\Maxlcp\wordpack}$ time,
where $\Maxlcp$ is the sum of all LCP values in the SLCP, which is always at least $\abs{\Comlcp}$, but can in fact be $\Theta(nm)$.

\subsection{Relationship between suffix sorting and LCE queries}
The LCE-problem is to preprocess a text $T$ such that subsequent LCE-queries $\lce(i,j) := \lcp(T[i..],T[j..])$ giving the length of the longest common prefix of the suffixes starting at positions $i$ and $j$ can be answered efficiently.
The currently best data structure for LCE is due to
\citet{billeLCE}, who proposed a deterministic algorithm  
that builds a data structure in $\Oh{n/\tau}$ space and $\Oh{n^{2+\epsilon}}$ time ($\epsilon>0$) answering LCE queries in $\Oh{\tau}$ time, for any $1 \le \tau \le n$.

Data structures for LCE and sparse suffix sorting are closely related, as shown in the 
following \namecref{obsLCEconnection}:

\begin{observation}\label{obsLCEconnection}
	Given a data structure that computes LCE in $\Oh{\tau}$ time for $\tau > 0$,
	we can compute sparse suffix sorting for $m$ positions in $\Oh{\tau m \lg m}$ time (using
	balanced binary search trees as outlined above).

	Conversely, given an algorithm computing the SSA and the SLCP of a text $T$ of length $n$ for $m$ positions in $\Oh{m}$ space and $\Oh{f(n,m)}$ time for some $f$, 
	we can construct a data structure in $\Oh{f(n,m)}$ time and $\Oh{m}$ space, answering LCE queries on $T$ in $\Oh{n^2/m^2}$ time~\cite{billeLCEPre},
	%JF is it important to cite Bille here?
	%its actually their idea, writing in that paper.
	(using a difference cover sampling modulo $n/m$~\cite{ksb2006}).
\end{observation}

As a tool for our sparse suffix sorting algorithm, we first develop a data structure for LCE-queries with the following properties.

\begin{theorem}\label{thmLCEtradeoff}
	There is a data structure
	using $\Oh{n/\tau}$ space
	that answers LCE queries in $\Oh{\lg^* n \tuple{\lg\tuple{n/\tau} + \tau^{\lg 3} \wordpack }}$ time, 
	where $1 \le \tau \le n$.
	We can build the data structure in $\Oh{n \tuple{\lg^*n + (\lookupTimeBest) / \tau + (\lg\tau) \wordpack }}$ time
	with additional $\Oh{\tau^{\lg 3} \lg^* n }$ words during construction.
\end{theorem}

An advantage of our data structure against the deterministic data structures in~\cite{billeLCE} is its faster construction time,
which is roughly $\Oh{n \lg n}$ time.


\section{Preliminaries}
Let $\Sigma$ be an ordered alphabet of size $\sigma$.
We assume that a character in $\Sigma$ is represented by an integer.
%NN but it does not need to represent the alphabetic order
%NN as long as the alphabetic order of two characters can be judged in constant time.
For a string $\textS \in \Sigma^{*}$, let $|\textS|$ denote the length of $\textS$.
For a position $i$ in $\textS$, let $\textS[i]$ denote the $i$-th character of $\textS$.
For positions $i$ and $j$, let $\textS[i..j] = \textS[i] \textS[i+1] \cdots \textS[j]$.
% where $\textS[i..j]$ represents the empty string if $i > j$.
For $\textV = \textS\textT\textU$ with $\textS,\textT,\textU \in \Sigma^*$, we call $\textS$, $\textT$ and $\textU$ a prefix, substring, suffix of $\textV$, respectively.
In particular, the suffix beginning at position $i$ is denoted by $\textS[i..]$.

An \intWort{interval} $\intervalI=[b..e]$ is the set of consecutive integers from $b$ to $e$, for $b\le e$. 
For an interval $\intervalI$, we use the notations $\ibeg{\intervalI}$ and $\iend{\intervalI}$ to denote the beginning and end of $\intervalI$;
i.e., $\intervalI = [\ibeg{\intervalI}..\iend{\intervalI}]$.
We write $\abs{\intervalI}$ to denote the length of $\intervalI$; i.e., $\abs{\intervalI}=\iend{\intervalI}-\ibeg{\intervalI}+1$.

\section{Answering LCE queries with ESP Trees}

Edit sensitive parsing (ESP) and ESP trees were proposed by \citet{Cormode2007sed} to approximate the edit distance with moves efficiently.
Here, we show that it can also be used to answer LCE queries.

\subsection{Edit Sensitive Parsing}\label{secESP}

The aim of the ESP technique is to decompose a string $\textT\in\Sigma^*$ into substrings of length~2 or~3
such that each substring of this decomposition is determined uniquely by its neighboring characters.
%niki: that is true if we implicitly assume the isomorphm that two strings are isomorph iff they contain characters with the same relative order (= the Suffix Array of both strings is identical)
To this end, it first identifies so-called \intWort{meta-blocks} in $\textT$, and then further refines these meta-blocks into \intWort{blocks} of length~2 or~3.

The meta-blocks are created in the following 3-stage process (see also \Cref{figESP} for an example):
\begin{enumerate}[(1)]
	\item Identify maximal regions of repeated symbols (i.e., maximal substrings of the form $c^\ell$ for $c\in\Sigma$ and $\ell\ge 2$). Such substrings form the \Type{1} meta-blocks.
\item Identify remaining substrings of length at least 2 (which must lie between two \Type{1} meta-blocks). Such substrings form the \Type{2} meta-blocks.
\item Any substring not yet covered by a meta-block consists of a single character and cannot have \Type{2} meta-blocks as its neighbors. Such characters $\textT[i]$ are fused with the \Type{1} meta-block to their right\footnote{The original version prefers the left meta-block, but we change it for a more stable behavior (cf. \Cref{figMixed})\label{footnoteMixedType}},
or, if $\textT[i]$ is the last character in $\textT$,
with the \Type{1} meta-block to its left.
The meta-blocks emerging from this are called \Type{M} (mixed).
\end{enumerate}
Meta-blocks of \Type{1} and \Type{M} are collectively called \intWort{repeating meta-blocks}.

Although meta-blocks are defined by the comprising characters, we treat them as intervals on the text range.
%TODO: move this sentence to a better place (where it matters).

\begin{figure}[t]
	\centerline{%
		\includegraphics[scale=1.0]{images/parsing}
	}
	\caption{We parse the string $\textT = \texttt{babababbbbbbbabbbbbabababaaaaab}$. 
		The string is divided into blocks, and each block gets assigned a new character (represented by the rounded boxes).
	} %\abs{T} = 14, \lg^*\abs{T} = 3$.}
	\label{figESP}
\end{figure}

Meta-blocks are further partitioned into \intWort{blocks}, each containing two or three characters from $\Sigma$.
Blocks inherit the type of the meta-block they are contained in.
How the blocks are partitioned depends on the type of the meta-block:
	
\begin{description}
	\item[Repeating meta-blocks.] 
		A repeating meta-block is partitioned greedily:
		create blocks of length three until there are at most four, but at least two characters left.
		If possible, create a single block of length 2 or 3; otherwise create two blocks, each containing two characters.
	\item[Type-2 meta-blocks.]
		A \Type{2} meta-block $\mu$ is processed in $\Oh{\abs{\mu} \lg^* \sigma}$ time 
		by a technique called \emph{alphabet reduction}~\cite{Cormode2007sed}.
		The first $\lg^* \sigma$ characters are blocked in the same way as repeating meta-blocks.
		Any remaining block $\beta$ is formed such that $\beta$'s interval boundaries are determined by
                $\textT[\max(\ibeg{\beta}-\lcontext, \ibeg{\mu})..\min(\iend{\beta}+\rcontext, \iend{\mu})]$,
		where $\lcontext := \upgauss{\lg^* \sigma} + 5$ and $\rcontext := 5$	(see {\cite[Lemma 8]{Cormode2007sed}}).
\end{description}

	We call the substring $\textT[\ibeg{\beta}-\lcontext..\iend{\beta}+\rcontext]$ the \intWort{local surrounding} of $\beta$, if it exists. 
	Blocks whose local surrounding exist are also called \intWort{surrounded}.
%JF: can 'surrounded' and 'local surrounding' be merged into 1 concept?
%niki: 'surrounded' = 'having a local surrounding'
%JF interior/inner??

Let $\tilde{\Sigma}\subseteq \Sigma^2\cup \Sigma^3$ denote the set of blocks resulting from ESP (the ``new alphabet'').
We use $\esp : \Sigma^* \rightarrow \tilde{\Sigma}^*$ to denote the function that parses a string by ESP and returns a string in $\tilde{\Sigma}^*$.


\subsection{Edit Sensitive Parsing Trees}\label{secDictAndNames}
Applying $\esp$ recursively on its output generates a context free grammar (CFG) as follows.
Let $\textT_0 := \textT$ be a string on an alphabet $\Sigma_0 := \Sigma$ with $\sigma_0 = \abs{\Sigma_0}$.
The output of $\textT_h := \esp^h(\textT) = \esp(\esp^{h-1}(\textT))$ is a sequence of blocks, which belong to a new alphabet %$\Sigma_{h+1}$
$\Sigma_{h}$ ($h>0$).
A block $b \in \Sigma_h$ contains a string $b \in \Sigma_{h-1}^*$ of length two or three.
Since each application of $\esp$ reduces the string length by at least 1/2,
there is a $k = \Oh{\lg \abs{\textT}}$ such that $\esp(\textT_k)$ returns a single block $\tau$.
We write $\idset := \bigcup_{1\le h \le k}\Sigma_h$ for the set of all blocks in $\textT_1, \textT_2, \ldots, \textT_k$.

We use a (deterministic) dictionary $\dic : \Sigma_h \rightarrow \Sigma_{h-1}^2 \cup \Sigma_{h-1}^3$ to map a block to its characters, for each $1 \le h \le k$.
The dictionary entries are of the form $b \rightarrow xy$ or $b \rightarrow xyz$, where $b \in \Sigma_h$ and $x,y,z\in \Sigma_{h-1}$.
The CFG for $\textT$ is represented by the non-terminals $\idset$, the terminals~$\Sigma_0$, the dictionary~$\dic$, and the start symbol~$\tau$.
This grammar exactly derives $\textT$.

Our representation differs from that of \citet{Cormode2007sed} because it does not use hash tables.

\begin{figure}[h]
	\centering{%
		\includegraphics[width=0.4\textwidth]{images/classicesptreeL}
	}
	\caption{Given the string $\textT = {\tt aaaaaaaaaaaaaaaabababa}$, we parse $\textT$ with ESP and build \etInst[\textT].
		Nodes/characters belonging to the same meta-block are connected by horizontal (repeating meta-block) or diagonal (\Type{2} meta-block) lines. 
	}
	\label{figClassicESP}
\end{figure}

\begin{figure}[t]
	\centering{%
		\includegraphics[width=\textwidth]{images/esptree}
	}
	\caption{Let $v$ be a node on $\espnode{\textT}_{h}$. 
		% The substring of $\espnode{\textT}_{h'}$ being occupied by $v$ comprises all descendants of $v$ on the height $h' < h$. 
		The subtree rooted at $v$ is depicted by the white, rounded boxes.
		The generated substring of $v$ is the concatenation of the white, bordered blocks on the lowest level in the picture.
		The meta-block $\mu$, on which $v$ is built, is highlighted by a horizontal hatching of the nodes on height $h-1$ contained in $\mu$.
	}
	\label{figESPtree}
\end{figure}


\begin{definition}
	The \intWort{ESP tree} $\etInst[\textT]$ of a string $\textT$ is a slightly modified derivation tree of the CFG defined above.\footnote{In the original version, it actually \emph{is} the derivation tree, but we modify it slightly for our convenience.}
	The internal nodes are elements of $\idset \setminus \Sigma_1$, and the leaves are from $\Sigma_1$. 
	Each leaf refers to a substring in $\Sigma_0^2$ or $\Sigma_0^3$.
	Its root node is the start symbol $\tau$.
\end{definition}
An example is given in \Cref{figClassicESP}.

For convenience, we count the height of nodes from $1$, so that the sequence of nodes on height $h$, denoted by $\espnode{\textT}_{h}$, is corresponding to $\textT_{h}$.
% In particular, the sequence of leaves~$\textT_1$ represents the blocks of $\esp[\textT]$.
% The sequence of nodes on height $h$ is denoted by $\espnode{\textT}_{h}$.
The \intWort{generated substring} of a node $\espnode{\textT}_h[i]$ is the substring of $\textT$ generated by the symbol $\textT_h[i]$ (applying $\dic$ recursively on $\textT_h[i]$).
Each node $v$ represents a block that is contained in a meta-block $\mu$, 
for which we say that $\mu$ \intWort{builds} $v$.
More precisely, a node $v := \espnode{\textT}_{h}[i]$ is said to be built on a meta-block represented by $\espnode{\textT}_{h-1}[b..e]$ iff 
$\espnode{\textT}_{h-1}[b..e]$ contains the children of $v$.
Like with blocks, nodes inherit the type of the meta-block on which they are built.
An overview of the above definitions is given in \Cref{figESPtree}.

{\bf Surrounded Nodes.}
A leaf is called surrounded iff its representing block on text-level is surrounded.
Given an internal node~$v$ on height~$h+1$ ($h \ge 1$) whose children are $\espnode{\textT}_h[\beta]$,
we say that $v$ is \intWort{surrounded} iff the nodes $\espnode{\textT}_h[\ibeg{\beta}-\lcontext..\iend{\beta}+\rcontext]$ are surrounded.


\subsection{Tree Representation}


We store the ESP tree as a CFG\@.
Every non-terminal is represented by a \intWort{name}.
The name is a pointer to a data-field, which is composed differently for leaves and internal nodes:
\begin{description}
	\item[Leaves.] A leaf stores a position $i$ and a length $l\in\{2,3\}$ such that $\textT[i..i+l-1]$ is the generated substring.
	\item[Internal nodes.] An internal node stores the length of its generated substring, and the names of its children.
		If it has only two children, we use a special, invalid name $\invalid$ for the non-existing third child 
		such that all data fields are of the same length.
\end{description}
%Since the names are pointers, evaluating $\dic(\beta)$ for some $\beta \in \idset$ is done by following the pointer that represents~$\beta$.
%JF out of place here (and more or less trivial)
This representation allows us to navigate top-down in the ESP tree by traversing the tree from the root, in time linear in the height of the tree.

We keep the invariant that the roots of \emph{isomorphic} subtrees have the \emph{same} names.
In other words, before creating a new name for the rule $b \rightarrow xyz$, we have to check whether there already exists a name for $xyz$.
To perform this look-up efficiently, we need also the \emph{reverse} dictionary of~$\dic$, with the right hand side of the rules as search keys.
We use a dictionary of size $\Oh{\abs{\textT}}$, supporting lookup and insert in $\Oh{\lookupTime}$ time.
% The dictionary looks up or inserts a node in $\Oh{\lookupTime}$ time. 

More precisely,
we assume there is a dictionary data structure, storing $n$ elements in $\Oh{n}$ space,
supporting lookup and insert in $\Oh{\lookupTime + \abs{l}\wordpack}$ time for a key of length $l$,
where $\lookupTime = \lookupTime(n)$ depends on $n$.
For instance, \citeauthor{betterSearching}'s DS~\cite{betterSearching} with word-packing supports $\lookupTime = \Oh{\lookupTimeBest}$.
%JF: TODO: this t_\lambda is too much in the intro. I suggest to instantiate it with the best
% possible in  the following theorem, and move the above paragraph to an appropriate point in the main text.
%niki: better?


\begin{lemma}\label{lemmaBuildESP}
An ESP tree of a string of length $n$ can be built in $\Oh{n \tuple{\lg^*n + \lookupTime }}$ time.
It consumes $\Oh{n}$ space.
\end{lemma}
\begin{proof}
	A name is inserted or looked-up in $\lookupUpper$ time.
	Due to the alphabet reduction technique, applying $\esp$ on a substring of length $l$ takes $\Oh{l \lg^* n}$ time, 
	returning a sequence of blocks of length at most $l/2$.
\end{proof}


\subsection{LCE queries on ESP trees}

ESP trees are fairly stable against edit operations:
The number of nodes that are differently parsed after 
prepending or appending a string to the input is upper bounded by $\Oh{\lg n \lg^* n}$~\cite[Lemma 11]{Cormode2007sed}.
To use this property in our context of LCE queries,
we consider nodes of $\etInst[\textT]$ that are still present in $\etInst[\textS\textT\textU]$;
a node $v$ in $\etInst[\textT]$ generating $\textT[i_{0}..j_{0}]$
is said to be \intWort{stable} iff, for \emph{all} strings $\textS$ and $\textU$, 
there exists a node $v'$ in $\etInst[\textS\textT\textU]$ that has the same name as $v$ and 
generates $(\textS\textT\textU)[|\textS|+i_{0}..|\textS|+j_{0}]$.
We also consider repeating nodes that are present with slight shifts;
a non-stable repeating node $v$ in $\etInst[\textT]$ generating $\textT[i_{0}..j_{0}]$
is said to be \intWort{semi-stable} iff, for \emph{all} strings $\textS$ and $\textU$, 
there exists a node $v'$ in $\etInst[\textS\textT\textU]$ that has the same name as $v$ and
generates a substring intersecting with $(\textS\textT\textU)[|\textS|+i_{0}..|\textS|+j_{0}]$.
Then, the proof of Lemma~9 of~\cite{Cormode2007sed} says that, for each height,
$\etInst[\textT]$ contains $\Oh{\lg^* n}$ nodes that are not (semi-)stable,
which we call \intWort{fragile}.
Since the children of the (semi-)stable nodes are also (semi-)stable,
there is a border on $\etInst[\textT]$ separating (semi-)stable nodes and fragile nodes.
% (TODO: Fig.).

In order to use semi-stable nodes to answer LCE queries efficiently,
we let each node have an additional property, called \intWort{surname}.
A node $v := \espnode{\textT}_{h}[i]$ is said to be \intWort{repetitive} 
iff there exists $\espnode{\textT}_{h'}[\intervalI]$ at some height $h' < h$ with $\textT_{h'}[\intervalI] = d^{\abs{\intervalI}}$,
where $\espnode{\textT}_{h'}[\intervalI]$ is the sequence of nodes on height $h'$ in the subtree rooted at $\espnode{\textT}_{h}[i]$ and $d \in \Sigma_{h'}$.
The surname of a repetitive node $v := \espnode{\textT}_{h}[i]$ is the name of a highest non-repetitive node in the subtree rooted at $v$.
The surname of a non-repetitive node is the name of the node itself.
It is easy to compute and store the surnames while constructing \eTree{}s.

The connection between semi-stable nodes and the surnames is based on the fact that
a semi-stable node is repetitive:
Let $u$ be the node whose name is the surname of a semi-stable node~$v$.
If $u$ is on height $h$, $v$'s subtree consists of a repeat of $u$'s on height~$h$.
A shift of $v$ can only be caused by adding $u$'s to the subtree of $v$.
So the shift is always a multiple of the length of the generated substring of $u$.



% This property is also used for pattern matching on ESP based grammer compressed text.

\begin{lemma}\label{lemmaLCE}
	Let $\textS$ and $\textT$ be strings with $\abs{\textS} \le \abs{\textT} \le n$.
	Given $\etInst[\textS]$ and $\etInst[\textT]$ built with the \emph{same} dictionary
	and two text-positions $1 \le i_\textS \le \abs{\textS}, 1 \le i_\textT \le \abs{\textT}$,
	we can compute $l := \lcp(\textS[i_{\textS}..], \textT[i_{\textT}..])$ in 
	$\Oh{\lg \abs{\textT} + \lg l \lg^* n}$ time.
\end{lemma}
\begin{proof}
	We compute the longest common prefix~$\textU$ of $\textS[i_\textS..]$ and $\textT[i_\textT..]$ 
	by traversing both ESP trees simultaneously from their roots.
	During the traversal, we trace the border that separates (semi-)stable nodes and fragile nodes of $\textU$.
Given two stable nodes, we can match their generated substrings by their names in constant time.
Matching a semi-stable node with a (semi-)stable node can be done in constant time due to the surnames:
Assume we visit two nodes $v$ and $v'$ (each belonging to one tree), where $v$ is semi-stable, $v'$ is (semi-)stable, and both have the same name,
but the compared positions are shifted.
Since $v$ and $v'$ are repetitive with the same surname,
the match with shift can be done in constant time by using their surname.
Since the number of visited fragile nodes is bounded by $\Oh{\lg l \lg^* n}$,
$\textU$ can be computed in $\Oh{\lg \abs{\textT} + \lg l \lg^* n}$ time,
where $\Oh{\lg \abs{\textT}}$ time is needed to traverse both trees from their roots to the first stable node.
\end{proof}


\subsection{Truncated \eTree{}s}\label{secTSESPImpl}
Building an \eTree{} over a string $\textT$ requires $\Oh{\abs{\textT}}$ words of space,
which might be too much in some scenarios.
Our idea is to truncate the \eTree{} at some fixed height, discarding the nodes in the lower part.
The truncated version stores just the upper part, while its (new) leaves refer to (possibly long) substrings of $\textT$.
The resulting tree is called the \intWort{truncated ET~(\teTree{})}.
More precisely, we define a height $\eta$ and delete all nodes at height less than $\eta$, which we call \intWort{lower nodes}.
A node higher than $\eta$ is called an \intWort{upper node}.
The nodes at height $\eta$ form the new leaves and are called \intWort{$\eta$-nodes}.
Similar to the former leaves, their names are pointers to their generated substrings appearing in $\textT$.
Remembering that each internal node has two or three children, 
an $\eta$-node generates a string of length at least $2^\eta$ and at most $3^\eta$.
So the maximum number of nodes in a \teTree{} of a string of length $n$ is $\numNodes{n}$. %$\numNodes{l} := l/2^\eta$.

Similar to leaves, we use the generated substring $\textS$ of an $\eta$-node~$v$ for storing and looking up $v$:
It can be looked up or inserted in $\Oh{\abs{\textS}\wordpack + \lookupEta}$ time.

These observations lead us to

\begin{lemma}\label{lemmaBuildTSESP}
We can build a \teTree{} of a string $\textT$ of length $n$ in 
$\Oh{n \tuple{\lg^*n + \eta\wordpack + \lookupTime/2^\eta }}$
time, using
$\Oh{3^\eta \lg^* n}$ words of working space.
The tree consumes $\Oh{\numNodes{n}}$ space.
\end{lemma}
\begin{proof}
Instead of building the ESP tree level by level, we compute the $\eta$-nodes node by node, from left to right.
We can split an ESP parsing of the whole string up into parts.
When a new part starts, we read $\lcontext$ characters of the end of the old part such that 
the parsing starts with $\lcontext$ old characters. 
These characters are necessary to reconstruct the meta-block boundaries,
and for the alphabet reduction to produce the same results like for the whole string.
In our case, a part contains the generated substring of one $\eta$-node.
Since an $\eta$-node generates a substring of at most $3^\eta$ characters, 
we parse $3^\eta+\lcontext$ characters on text level at once, creating lower nodes.
In order to parse a string of lower nodes by ESP, we have to give them names.

%Although we do not store the lower nodes in the dictionary, we have to give them temporary names so that ESP can work on them.
The names of the lower nodes are created temporarily, and are not stored in the dictionary.
Since two $\eta$-nodes have the same name iff their substrees are isomorph, 
the task is to create the name of a lower node based on its subtree, and restore its name without using~$\dic$.
To this end, we use the generated substring of a lower node as its name.
%By saving $\lcontext$ characters and nodes on each height.
%Since the name of an $\eta$-node is der, we have to create its subtree and its local surrounding.

{\bf Working Space.}
%We need additional working space for constructing an $\eta$-node, since we do not store its subtree containing lower nodes.
%Consider that we want to build an $\eta$-node.
We need $\Oh{3^\eta \lg^* n}$ words of working space in order to construct an $\eta$-node $v$:
The name of~$v$ is determined by its subtree and its local surrounding.
%since we only have to determine those nodes that are occupied by $v$, or are in the local surrounding of $v$.
%We keep these nodes in memory, taking $\Oh{3^\eta \lg^* n}$ words of working space.
So we can construct $v$ after computing its subtree and its local surrounding.
Both contain lower nodes that we store temporarily in the working space.
With a pointer based representation, the subtree of an $\eta$-node needs $\Oh{3^\eta}$ words of working space.
Since we additionally store its local surrounding, we come to $\Oh{3^\eta \lg^* n}$ words of working space.
%We do not save the names of the lower nodes in the reverse dictionary of~$\dic$.

{\bf Time.} 
%The time is lower-bounded by the results of \Cref{lemmaBuildESP} for the \eTree{}.
The time bound $\Oh{n \lg^* n}$ for the repeated application of the alphabet reduction is the same as in \Cref{lemmaBuildESP}.


While parsing a string of lower nodes, the ESP compares the name of two adjacent lower nodes.
Comparing two lower nodes is done by naively comparing the characters represented by their names.
We compare two lower nodes during the construction of an $\eta$-node.
Let us take the set of lower nodes on height $1 \le h < \eta$.
Their generated substrings have a length of $n$.
So we spend $\Oh{n \wordpack}$ time in total for comparing two lower nodes on the same height $1 \le h < \eta$.
By summing over all heights, these comparisons take $\Oh{n \eta \wordpack}$ time in total.

% Since the sum of the lengths of all substrings
% generated by the $\eta$-nodes is $l$, 
By the same argument,
maintaining the names of all $\eta$-nodes takes $\Oh{n\wordpack + \lookupEta \numNodes{n} }$ time.

A name is looked-up in $\Oh{\lookupUpper}$ time for an upper node.
Since the number of upper nodes is bounded by $\numNodes{n}$,
maintaining the names of the upper nodes takes $\Oh{\lookupUpper \numNodes{n}}$ time.
This time is subsumed by the lookup time for the $\eta$-nodes.
\end{proof}

\begin{lemma}\label{lemmaTruncatedLCE}
	Let $\textS$ and $\textT$ be strings with $\abs{\textS}, \abs{\textT} \le n$.
	Given $\etInst[\textS]$ and $\etInst[\textT]$ built with the \emph{same} dictionary
	and two text-positions $1 \le i_\textS \le \abs{\textS}, 1 \le i_\textT \le \abs{\textT}$,
	we can compute $\lcp(\textS[i_{\textS}..], \textT[i_{\textT}..])$ in 
	$\Oh{\lg^*n (\lg (\numNodes{n}) + 3^\eta \wordpack )}$ time.
\end{lemma}
\begin{proof}
\Cref{lemmaLCE} gives us the time bounds when dealing with an \eTree{}. 
According to the \namecref{lemmaLCE}, 
there are at most $\Oh{\lcontext + \rcontext}$ many comparisons that examine the leaves of some $\eta$-nodes.
Unfortunately, we cannot perform any node comparison on a height lower than $\eta$ on the truncated trees; 
instead we take the name of each respective $\eta$-node leading us to a substring whose length is upper-bounded by $3^\eta$.
Comparing both $\eta$-nodes is done by checking at most $3^\eta \wordpack$ words.
Since the height of the \teTree{} is bounded by $\Oh{\lg\numNodes{n}}$, 
we use up to $\Oh{\lg^*n \lg (\numNodes{n})}$ time for the upper nodes.
\end{proof}

With $\tau := 2^\eta$ we get \Cref{thmLCEtradeoff}.


\section{Sparse Suffix Sorting}
The sparse suffix sorting problem asks for the order of suffixes starting at certain positions in a text~$T$.
In our case, these positions can be given online, i.e., sequentially and in an arbitrary order.
We collect them conceptually in a dynamic set~$\Pos$.
Due to the online setting, we represent the order of the suffixes $\Suf(\Pos)$ starting at those positions by a dynamic, self-balancing binary search tree (e.g., an AVL tree).
Each node of the tree is associated with a distinct suffix in $\Suf(\Pos)$, and the lexicographic order is used as the sorting criterion.

Borrowing the technique of \citet{Irving2003sbs}, an AVL tree on a set of strings~$\SetStr$ can be augmented with LCP values so that
we can compute
$l := \max \{ \lcp(\textS, \textT) \mid \textS \in \SetStr \}$ 
for a string $\textT$
in $\Oh{l \wordpack + \lg \abs{\SetStr}}$ time.
Inserting a new string into the tree is supported in the same time complexity.
\citet{Irving2003sbs} called this data structure the \intWort{\SAVLT} on $\SetStr$; we denote it by $\SAVL(\SetStr)$.

Given a text~$T$ of length~$n$, we will use $\SAVL(\Suf(\Pos))$ as a representation for $\SSA[T,\Pos]$ and $\SLCP[T,\Pos]$.
%where $\Suf(\Pos)$ denotes the set of suffixes of $T$ starting at the positions in $\Pos$.
Our goal is to build $\SAVL(\Suf(\Pos))$ efficiently.
However, inserting suffixes naively suffers from the lower bound $\Om{n \abs{\Pos} \wordpack}$ on time.
How to speed up the comparisons by exploiting a data structure for LCE queries is topic of this section.
%The workhorse will be a modified edit sensitive parsing tree, whose definition follows in \Cref{secHSP}.

\subsection{Abstract Algorithm}\label{secAbstAlgo}

Starting with an empty set of positions~$\Pos = \emptyset$,
our algorithm updates $\SAVL(\Suf(\Pos))$ on the input of every new text-position,
involving LCE computation between the new suffix and some suffixes stored in $\SAVL(\Suf(\Pos))$.
Our idea is that creating a mergeable LCE data structure on the read substrings may be helpful for later queries.
In more detail, we need a data structure that 
\begin{itemize}
	\item answers LCE queries on two substrings covered by instances of this data structure,
	\item is mergeable in such a way that the merged instance answers queries faster than 
		performing a query over both former instances separately.
\end{itemize}
We call this abstract data type \intWort{dynamic LCE~(\DynLCE{})}; it supports the following operations:

\begin{itemize}
	\item $\DynLCEInst[\textT]$ constructs a \DynLCE{} $M$ on a substring $\textT$ of $T$. Let $M.\memtext$ denote the string $\textT$ on which $M$ is constructed.
	\item {\tt LCE}$(M_1,M_2, p_1,p_2)$ computes $\lcp(M_1.\memtext[p_1..],M_2.\memtext[p_2..])$, where $p_i \in [1..\abs{M_i.\memtext}]$ for $i=1,2$.
	\item {\tt merge}$(M_1, M_2)$ merges two \DynLCE{}s $M_1$ and $M_2$ such that the output is a \DynLCE{} 
		on the concatenation of $M_1.\memtext$ and $M_2.\memtext$.
\end{itemize}
We use the expression $\timeConstruct{\abs{\textT}}$ to denote the construction time on a string $\textT$.
Further,
$\timeLCE{\abs{\textS}+\abs{\textT}}$ and $\timeMerge{\abs{\textS}+\abs{\textT}}$ denote the LCE query time and the time for merging on two strings $\textS$ and $\textT$, respectively.
Querying a \DynLCE{} built on a string of length $\ell$ is faster than the word-packed character comparison
iff $\ell = \Om{ \timeLCE{\ell} \lg n / \lg \sigma}$.
Hence, there is no point in building a \DynLCE{} on a text smaller than $\gap := \Ot{\timeLCE{\gap} \lg n / \lg \sigma}$.

We store the text intervals covered by the \DynLCE{}s such that we know the text-positions where querying a \DynLCE{} is possible.
Such an interval is called an \intWort{\LCEI{}}.
An \LCEI{} $\intervalI$ stores a pointer to
its \DynLCE{} data structure $M$, and
an integer $i$ such that 
$M.\memtext[i..i+\abs{\intervalI}-1] = T[\intervalI]$.
The \LCEI{}s themselves are maintained in a self-balancing binary search tree of size $\Oh{\abs{\Pos}}$, 
storing their starting positions as keys.

\ifthenelse{\boolean{withAlgo}}{%
\begin{algorithm}[t]
\DontPrintSemicolon{} % Some LaTeX compilers require you to use \dontprintsemicolon instead
Let $\intervalI.\memref$ return the resp. \DynLCE{} of a \LCEI{} $\intervalI$. \;
$B \gets $ global binary search tree of \LCEI{}s \;
$p \mapsto B.{\tt lowerBound}(p)$ := interval with \emph{largest} starting position smaller or equal to $p$ \;
$p \mapsto B.{\tt upperBound}(p)$ := interval with \emph{smallest} starting position larger than $p$ \;
\function(\tcp*[h]{called by \Cref{algoSparseSuf} to find the insertion position for $\hat{p}$}){{\tt lce}($p,p'$)}{%
	$\intervalI \gets B.{\tt lowerBound}(p)$ and
	$\intervalJ \gets B.{\tt lowerBound}(p')$ \;
	\lIf{$\iend{\intervalI} > p$ and $\iend{\intervalJ} > p'$}{%
		$l \gets {\texttt lce}(\intervalI.\memref,\intervalJ.\memref,p,p')$
}
\Else{%
	$\intervalI \gets B.{\tt upperBound}(p)$ and
	$\intervalJ \gets B.{\tt upperBound}(p')$ \;
	$l \gets {\tt naivecmp}(T,p,p',\min\tuple{\ibeg{\intervalI}-p,\ibeg{\intervalJ}-p'})$ \tcp*[h]{compare naively until reaching areas covered by $B$}
}
	$p \gets p+l+1$ and
	$p' \gets p'+l+1$ \;
	\lIf(\tcp*[h]{Found mismatch}){$T[p] \not= T[p']$}{% 
		\Return{$l$}
	}
	\Return{$l + {\tt lce}(p,p')$} \tcp*{reached either the begin or end of an covered by $B$}
}
\caption{Hybrid LCE Algorithm -- Locating Process}
\label{algoHybridLCE}
\end{algorithm}
}{}%withAlgo

\ifthenelse{\boolean{withAlgo}}{%
\begin{algorithm}[t]
\DontPrintSemicolon % Some LaTeX compilers require you to use \dontprintsemicolon instead
$S \gets \SAVL(\Suf(\Pos))$ \tcp*{global \SAVLT{} representing SSA and SLCP}
\function(\tcp*[h]{online query with a fresh text position $\hat{p}$}){add($\hat{p} \in [1,n] \setminus \Pos$)}{%
	$v \gets S.{\tt root}$ \tcp*{locate insertion position of $T[\hat{p}..]$ in $S$}
	\lWhile(\tcp*[h]{perform on each depth an LCE query with a suffix, use \Cref{algoHybridLCE}}){$v$ is not a leaf}{%
		$v \gets S.{\tt locateChild}(v, \hat{p}, \lce)$ 
	}
	$\bar{p} \gets \mlcparg{\hat{p}}$ and
	$l \gets {\tt lce}(\bar{p}, \hat{p})$ \tcp*{already computed above}
	$S$.{\tt insert}$(v,\hat{p})$ \tcp*{Add the suffix $T[\hat{p}..]$ to SSA} 
	\lIf(\tcp*[h]{\ref{itemIntervallength}}){$l < \gap$}{%
		\Return{}
	}
	$A \gets B.{\tt intersectWith}([\bar{p}-\gap,\bar{p}+l+\gap-1])$ : list of \LCEI{}s \;
	$A \gets A \cup B.{\tt intersectWith}([\hat{p}-\gap,\hat{p}+\gap+l-1])$ \;
	$U \gets \bigcup_{\intervalI \in A} \intervalI$ \tcp*{union over the intervals that are interesting for merging}
	\lIf(\tcp*[h]{\ref{itemIntervalcover} not violated}){$\abs{([\hat{p},\hat{p}+l-1] \cup [\bar{p},\bar{p}+l-1]) \setminus U} < \gap$}{%
		\Return{}
	}
	\For{each interval $\intervalI \in ([\hat{p},\hat{p}+l-1] \cup [\bar{p},\bar{p}+l-1]) \setminus U$}{%
		either assign $\intervalI.\memref$ to a \DynLCEInst{} (\ref{ruleReference}) or set $\intervalI.\memref \gets {\DynLCEInst[\substr{T}{\intervalI}]}$  (\ref{ruleCreate}) \;
		$B$.{\tt insert}($\intervalI$) and 
		$A$.{\tt insert}($\intervalI$) \;
	}
	sort $A$ ascendingly by the starting positions of its intervals \;
$\intervalI := A.{\tt pop}()$ \tcp*{use $A$ like a queue} 
	\While(\tcp*[h]{enforce~\ref{itemIntervalgap}}){$A$ is not empty}{%
		$\intervalJ \gets A.{\tt pop}()$ \;
		\If(\tcp*[h]{only if $\intervalI \subset [\hat{p},\hat{p}+l-1], \intervalJ \subset [\bar{p},\bar{p}+l-1]$ or vice versa}){$\iend{\intervalI}+1 \not= \ibeg{\intervalJ}$}{%
			{\bf continue} \;
		}
			$\intervalI' \gets \intervalI \cup \intervalJ$ \tcp*{merge both intervals}
			$\intervalI'.\memref \gets {\tt merge}(\intervalI.\memref, \intervalJ.\memref)$ \tcp*[h]{apply~\ref{ruleMerge}} \;
			$B.{\tt delete}(\intervalI)$ and $B.{\tt delete}(\intervalJ)$ \;
			$B.{\tt insert}(\intervalI')$ 
	%}
	}
	$\Pos \gets \Pos \cup \menge{\hat{p}}$ \;
}
\caption{Sparse Suffix Sorting}
\label{algoSparseSuf}
\end{algorithm}
}{}%withAlgo

For a new position $1 \le \hat{p} \le \abs{T}, \hat{p} \not\in \Pos$,
updating $\SAVL(\Suf(\Pos))$ to $\SAVL(\Suf(\Pos \cup \{ \hat{p} \}))$
involves two parts: first locating the insertion node for $\hat{p}$ in $\SAVL(\Suf(\Pos))$, and then updating the set of \LCEI{}s.

{\bf Locating. } 
The \SAVLT{} performs an LCE computation for each node encountered while locating the insertion point of $\hat{p}$. 
Assume that the task is to compare the suffixes $T[i..]$ and $T[j..]$ for some $1 \le i,j \le \abs{T}$. 
First check whether the positions $i$ and $j$ are contained in an \LCEI{}, in \Oh{\lg m} time.
If both positions are covered by \LCEI{}s, 
then query the respective $\DynLCE$s.
Otherwise, look up the position where the next \LCEI{} starts.
Up to that position, naively compare both substrings.
Finally, repeat the above check again at the new positions, until finding a mismatch.
After locating the insertion point of $\hat{p}$ in $\SAVL(\Suf(\Pos))$, 
we obtain 
$\bar{p} := \mlcparg{\hat{p}}$ and
$l := \mlcp{\hat{p}}$
as a byproduct, where
$\mlcparg{p} := \argmax_{p' \in \Pos, p \neq p'} \lcp(T[p..], T[p'..])$ 
and $\mlcp{p} := \lcp(T[p..], T[\mlcparg{p}..])$
for $1 \le p \le \abs{T}$.


%Assume that we have already constructed $\SAVL(\Suf(\Pos))$ by inserting positions into $\Pos$.
%JF sentence out of place.
{\bf Updating. }
The \LCEI{}s are updated dynamically, subject to the following constraints~(see \Cref{figConstraints}):
\begin{enumerate}[leftmargin=*,label={Constraint~\arabic*:},ref={Constraint~\arabic*}]
	\item The length of each \LCEI{} is at least $\gap$. \label{itemIntervallength}
	\item For every $p \in \Pos$ the interval $[p..p+\mlcp{p}-1]$ is covered by an \LCEI{}
	  \emph{except at most} $\gap$ positions at its left and right ends. \label{itemIntervalcover} 
  \item There is a gap of at least $\gap$ positions between every pair of \LCEI{}s. \label{itemIntervalgap}
\end{enumerate}
These constraints guarantee that there is at most one \LCEI{} that intersects with $[p..p+\mlcp{p}-1]$ for a $p \in \Pos$.
\begin{figure}[h]
	\centering{%
		\includegraphics[width=\textwidth]{images/constraints}
	}
	\caption{Sketch of two \LCEI{}s and the constraints.}
	\label{figConstraints}
\end{figure}

\begin{figure}[t]
	\centerline{%
		\includegraphics[scale=1.0]{images/algorules}
	}%centerline
	\caption{%
		The interval $\intervalI := [\hat{p}+i..\hat{p}+j]$ is not yet covered by an \LCEI{}, but belongs
		to $[\hat{p}..\hat{p}+l-1]$. It is accompanied by $\intervalJ := [\bar{p}+i..\bar{p}+j]$.
	}
	\label{figAlgoRules}
\end{figure}

The following instructions will satisfy the constraints:
If $l < \gap$, we do nothing.
Otherwise, we have to care about~\ref{itemIntervalcover}.  
Fortunately, there is at most one position in $\Pos$ that possibly invalidates~\ref{itemIntervalcover} after adding $\hat{p}$, and this is $\bar{p}$;
otherwise, by transitivity, we would have created some larger \LCEI{} previously.
Let $U \subset [1..n]$ be the positions that belong to an \LCEI{}.
The set $[\hat{p}..\hat{p}+l-1] \setminus U$ can be represented as a set of disjoint intervals of maximal length.
For each interval $\intervalI := [\hat{p}+i..\hat{p}+j] \subset [\hat{p}..\hat{p}+l-1]$ of that set (for some $0 \le i \le j < l$, see \Cref{figAlgoRules}), 
apply the following rules with $\intervalJ := [\bar{p}+i..\bar{p}+j]$ sequentially:
\begin{enumerate}[leftmargin=*,label={Rule~\arabic*:},ref={Rule~\arabic*}]
	\item \label{ruleReference}	If $\intervalJ$ is a sub-interval of an \LCEI{}, 
		then declare $\intervalI$ as an \LCEI{} and let it refer to the \DynLCE{} of the larger \LCEI{}.
	\item \label{ruleIntersect}
		If $\intervalJ$ intersects with an \LCEI{} $\intervalK$, 
		enlarge $\intervalK$ to $\intervalK \cup \intervalJ$, enlarging its corresponding \DynLCE{}
		(We can enlarge an \DynLCE{} by creating a new instance and merge both instances).
		Apply~\ref{ruleReference}.
	\item \label{ruleCreate} 
		Otherwise, create a \DynLCE{} on $\intervalI$, and make $\intervalI$ to an \LCEI{}.
	\item  \label{ruleMerge} 
		If~\ref{itemIntervalgap} is violated, then a newly created or enlarged \LCEI{} is adjacent to another \LCEI{}.
		Merge those \LCEI{}s and their \DynLCE{}s.
\end{enumerate}
We also need to satisfy~\ref{itemIntervalcover} on $[\bar{p}..\bar{p}+l-1]$.
To this end, update $U$, compute the set of disjoint intervals $[\bar{p}..\bar{p}+l-1] \setminus U$ and apply the same rules on it.

Although we might create some \LCEI{}s covering less than $\gap$ characters, we
will restore~\ref{itemIntervallength} by merging them with a larger \LCEI{} in~\ref{ruleMerge}.
In fact, we introduce at most two new \LCEI{}s.
\ref{itemIntervallength} is easily maintained, since we will never shrink an \LCEI{}.

\begin{lemma}\label{thmAbstractExtraSpace}
	Given a text $T$ of length $n$ that is loaded into RAM,
  the SSA and SLCP of $T$ for a set of $m$ arbitrary positions can be computed deterministically in 
  $\Oh{\timeConstruct{\abs{\Comlcp}} + \timeLCE{\abs{\Comlcp}} m \lg m + m \timeMerge{\abs{\Comlcp}}}$ time.
\end{lemma}
\begin{proof}
	The analysis is split into managing the \DynLCE{}s, and the LCE queries:
	\begin{itemize}
		\item 
			We build \DynLCE{}s over at most $\abs{\Comlcp}$ characters of the text.
			So we need at most $\timeConstruct{\abs{\Comlcp}}$ time for constructing all \DynLCE{}s.
			During the construction of the \DynLCE{}s we spend at most $\Oh{\abs{\Comlcp}\wordpack} = \Oh{\timeConstruct{\abs{\Comlcp}}}$ time on naive searches.
		\item 
			The number of merge operations on the \LCEI{}s 
			is upper bounded by $4m$ in total, since we create at most two new \LCEI{}s for every position in $\Pos$.
			So we spend at most $4m \timeMerge{\abs{\Comlcp}}$ time for the merging.
		\item LCE queries involve either naive character comparisons or querying a \DynLCE{}.
			We change the comparison technique (LCE by \DynLCE, or naive word-comparison) at most $2m$ times, until finding a mismatch.
			For the latter, the overall time is bounded by $\Oh{\timeConstruct{\abs{\Comlcp}} + \timeLCE{\abs{\Comlcp}} m \lg m}$:
			\begin{itemize}
				\item Since we do not create an \LCEI{} on two substrings with an LCP-value smaller than $\gap$ (\ref{itemIntervallength}), 
					we spend at most $\Oh{\gap m \lg m \wordpack} = \Oh{\timeLCE{\abs{\Comlcp}} m \lg m}$ time on those substrings.
					\item Otherwise, the time is already subsumed by the total time for \DynLCE{}-creation.
			\end{itemize}
			For the former, the LCE queries take at most $\Oh{\timeLCE{\abs{\Comlcp}} m \lg m}$ overall time.

			Looking up an \LCEI{} is done in $\Oh{\lg m}$ time. 
			For each LCE query, we look up at most $2m$ \LCEI{}s,
			summing to $\Oh{m \lg m}$ time,
			which is subsumed by the time bound for LCE queries.
	\end{itemize}
\end{proof}

\subsection{Sparse Suffix Sorting with ESP Trees}
We will show that the ESP tree is a suitable data structure for \DynLCE{}.
In order to merge two ESP trees, we use a \emph{common} dictionary~$\dic$ that is stored \emph{globally}.
Fortunately, it is easy to combine two \eTree{}s by updating just a handful of nodes, which are fragile.

Here we explain which nodes in $\etInst[\textT]$ are fragile.
Whether a node is fragile or not is determined bottom up and depending on the type of meta-block $\mu$.

{\bf If $\mu$ is \Type{2}.}
Since a node is parsed based on its local surrounding,
a node is fragile iff it is not surrounded or its local surrounding contains a fragile node.

{\bf If $\mu$ is a repeating meta-block.}
A node~$v$ of a repeating meta-block is determined among others by its children and its three left siblings:
If one of $v$'s children is fragile, $v$ is fragile, too.
In addition, if one of $v$'s three left siblings is fragile,
the type of the meta-block to which $v$ belongs can switch from \Type{2} to \Type{M} and vice versa (see~\Cref{tableBadType3Beginning}).
The type switch may change the contents of~$v$.

Moreover, if $\mu$ contains a fragile node, or one of the three right-most nodes in the meta-block preceeding $\mu$ is fragile,
we treat the last two nodes of $\mu$ as fragile:
Since the greedy blocking partitions a meta-block from left to right,
the last two nodes absorb always the remaining characters (see~\Cref{tableRepeatingAs}).


\begin{figure}[t]
	\centerline{%
			\includegraphics[scale=1.0]{images/fragile}
	}%centerline
	\caption{%
		We prepend the string {\tt aab} to the text ${\tt a}^k$ character by character, and compute the parsing each time.
		The last row shows an example, where a former \Type{1} meta-block changes to \Type{M}, 
		although it is right of a \Type{2} meta-block.
		Here, $k \mod 3 = 2$.}
	\label{tableBadType3Beginning}
\end{figure}

\begin{figure}[t]
	\centerline{%
		\includegraphics[scale=1.0]{images/greedyparsing}
	}%centerline
	\caption{%
The greedy blocking is related to the Euclidean division by three.
The remainder $k \mod 3$ is determined by the number of characters in the last two blocks (here, $k \mod 3 = 0$).
In this example, \esp\ created a single, repeating meta-block on each input.
	}
	\label{tableRepeatingAs}
\end{figure}


\begin{figure}[t]
	\centering{%
		\includegraphics[scale=0.8]{./images/hspmerge.pdf}
	}
	\caption{We merge $\etInst[{\tt{(ab)}^6a^6}]$ with $\etInst[{\tt a^{24}}]$ (both at the top) to $\etInst[{\tt {(ab)}^6a^{30}}]$ (bottom tree).
		Reparsing a repeating meta-block of the right tree changes its fragile nodes.
			}
\label{figHspmerge}
\end{figure}

\begin{lemma}\label{lemmaTreeCombine}
	Given two strings $\textS,\textT \in \Sigma^*$, assume that we have already created $\etInst[\textS]$ and $\etInst[\textT]$.
	Merging both trees into $\etInst[\textS\textT]$ takes
	$\Oh{\lookupTime \tuple{\lcontext \lg \abs{\textT} +  \rcontext \lg \abs{\textS}}  }$ time.
\end{lemma}
\begin{proof}
	We recompute some nodes located at the splice of both trees, from the bottom up to the root:
	At each height $h$, check the $\rcontext$ rightmost nodes of $\espnode{\textS}_h$, 
	and some leftmost nodes of $\espnode{\textT}_h$ until finding a stable node in $\espnode{\textT}_h$.
%	(do not revalidate whether a node of $\etInst[\textT]$ is a solid node of $\etInst[\textS\textT]$).
	If the leftmost $\lcontext$~nodes of $\espnode{\textT}_h$ are \Type{2} nodes, 
	recompute the ESP for these nodes.
	After processing these $\lcontext$~nodes we encounter a stable node, and stop.
	Otherwise, we have to fix a repeating meta-block $\mu$ (like in \Cref{figHspmerge}).
	We restructure $\mu$ with the following operations:
	Go to $\mu$'s right end in $\Oh{\lg \abs{\mu}}$ time, involving tree climbing 
	and node skipping based on the subtree sizes and the names.
	Then reparse the fragile nodes.
	Since the fragile property is propagated upwards, we recompute its ancestors and their fragile sibling nodes.
	We mark the recomputed fragile nodes such that we will not recompute them again.
	By this strategy every solid \Type{2} node gets marked before we visit it during the re-computation of the \Type{2} nodes in the first case.
	Since there are $\Oh{\lcontext \lg \abs{\textT}}$ fragile nodes,
        we spend $\Oh{\lcontext \lookupTime \lg \abs{\textT}}$ time for the fragile nodes in total.
	Finally, climb up one height on both trees.
\end{proof}

We conclude that the \eTree{}s are a representation of \DynLCE{}.
The following theorem combines the results of \Cref{thmAbstractExtraSpace,lemmaTreeCombine}.

\begin{theorem}\label{thmExtraSpace}
	Given a text $T$ of length $n$ and a set of $m$ text positions $\Pos$,
$\SSA[T,\Pos]$ and $\SLCP[T,\Pos]$ can be computed in 
  $\Oh{\abs{\Comlcp} (\lg^* n + \lookupTime) +  m \lg m \lg n \lg^* n}$ time.
\end{theorem}
\begin{proof}
\ifthenelse{\boolean{withAlgo}}{%
	Since we will construct \DynLCE{}s (the \eTree{}s) on \emph{disjoint} parts of the text $T$,
	the number of names is bounded by $\numnames \le 2 \abs{\Comlcp} \le 2n$ during the execution of \Cref{algoSparseSuf}.
}{}%withAlgo
We have $\timeLCE{\abs{\Comlcp}} = \Oh{\lg^*n \lg n}$ due to \Cref{lemmaLCE},
$\gap = \Ot{\lg^*n \lg^2 n / \lg \sigma}$,
$\timeConstruct{\abs{\Comlcp}} = \Oh{\abs{\Comlcp} \tuple{\lg^*n + \lookupTime }}$ due to \Cref{lemmaBuildESP},
and $\timeMerge{\abs{\Comlcp}} = \Oh{\lookupTime \lg n \lg^* n}$ due to \Cref{lemmaTreeCombine}.
Actually, the costs for merging is already upper bounded by the tree creation:
Let $\delta \le m$ be the number of \LCEI{}s.
Since each \eTree{} covers at least $\gap$ characters, $\delta \gap \le \Oh{\abs{\Comlcp}}$ holds, and we get
$\delta \timeMerge{\abs{\Comlcp}} \le \abs{\Comlcp} \timeMerge{\abs{\Comlcp}} /\gap = \Oh{\abs{\Comlcp} \lookupTime}$ overall time for merging.

By applying these results to \Cref{thmAbstractExtraSpace} we get the claimed time bounds.
\end{proof}

\section{Hierarchical Stable Parsing}
Remembering the outline in the introduction, the key idea is to solve the limited space problem by storing \DynLCE{}s in text space.
Taking two \LCEI{}s on the text containing the same substring, 
we overwrite \emph{one} part while marking the \emph{other} part as a reference.
By choosing a suitably large $\eta$, we can overwrite the text of one \LCEI{} with a \teTree{} whose $\eta$-nodes refer to 
substrings of the other \LCEI{}. 
Merging two \teTree{}s involves a reparsing of some $\eta$-nodes (cf.~\Cref{figClassicESP} and \Cref{figClassicESPFragile}).
Assume that we want to reparse an $\eta$-node $v$, and that its generated substring gets enlarged due to the parsing.
%We obtain its new name by re-computing its generated substring.
%In case that the generated substring gets enlarged, 
We have to locate a substring on the text that contains its new generated substring~$\textS$.
Although we can create a suitable large string containing~$\textS$ 
by concatenating the generated substrings of its preceding and succeeding siblings,
these $\eta$-nodes may point to text intervals that may not be consecutive.
Since the name of an $\eta$-node is the representation of a \emph{single} substring,
we have to search for a substring equal to~$\textS$ in the text.
Because this would be too inefficient,
we will show a slight modification of the ESP technique that circumvents this problem.
%Instead, we will show that with a slight modification of the ESP technique, 
%the \teTree{}s can be used for solving the online sparse suffix sorting problem in text space with $\Oh{m}$ additional space.

\begin{figure}[h]
	\centering{%
		\includegraphics[width=0.4\textwidth]{images/classicesptreeR}
	}
	\caption{We take $\textT$ from \Cref{figClassicESP}, and prepend the character~{\tt a} to it.
	Parsing ${\tt a} \textT$ with ESP generates a tree that is very different to \Cref{figClassicESP}.
	}
	\label{figClassicESPFragile}
\end{figure}

\subsection{Hierarchical Stable Parse Trees}\label{secHSP}
Our modification, which we call \textit{hierarchical stable parse trees} or \intWort{HSP trees}, \
affects only the definition of meta-blocks.
The factorization of meta-blocks is done by relaxing the check whether two characters are equal;
instead of comparing names we compare by surname.\footnote{The check is relaxed since nodes with different surnames cannot have the same name.}
This means that we allow meta-blocks of \Type{1} to contain heterogeneous elements as long as they share the same surname~(cf.~\Cref{figDiffSurname}).
The other parts of the algorithm are left untouched; in particular, the alphabet reduction uses the names as before.
We write $\hInst[\textT]$ for the resulting parse tree when HSP is applied to a string $\textT$.

% The representation of an HSP tree includes a bit at every repetitive node, indicating whether the surname is the name of an \emph{internal} node or of a \emph{leaf}, since their names are treated separately.
%dk: This sentence now seems out-of-place. Move upwards?
%TI: I do not think this is something important to note. Theoretitians do not mind it while practicioners implement it as they want.
%dk: ok

We directly follow that
\begin{enumerate}[(a)]
	\item the generated substring of a repetitive node is a repetition. 
	%dk: this item is a property of repetitive and thus has to be moved up to its definition
	\item \label{itHSPPropsRep} consecutive, repetitive nodes with the same surname are grouped into one meta-block~$\mu$. 
		The generated substring of each node in~$\mu$ is a repetition with the same root, but with possibly different exponents.
		The exponents of the generated substrings of the last two nodes cannot be larger than the exponents of the other generated substrings.
	\item A node~$v$ of a repeating meta-block~$\mu$ is non-repetitive iff $\mu$ is \Type{M} and 
	contains the single character that got merged with a former repetitive meta-block. 
	The node~$v$ can only be located at the begin or end of~$\mu$.
	If $\mu$ is the leftmost or rightmost meta-block, this node cannot be surrounded~(see \Cref{figGoodMixed}).
	By~\ref{itHSPPropsRep}, $v$ is either stable or non-surrounded.
\end{enumerate}

\begin{lemma}\label{lemmaBuildSESP}
An HSP tree on an interval of length $l$ can be built in 
$\Oh{l \tuple{\lg^*n + \lookupTime }}$
time.
It consumes $\Oh{l}$ space.
\end{lemma}
% \begin{proof}
% 	The surnames can be computed in constant time per node, because
% 	the surname of a repetitive node $v$ is one of the names or surnames of its two or three children.
% 	Since everything else can be implemented like for the ESP trees, we get the same results as in \Cref{lemmaBuildESP}.
% \end{proof}

\begin{figure}[h]
	\centering{%
		\includegraphics[width=0.3\textwidth]{images/diffsurname}
	}
	\caption{The HSP creates nodes based on the surnames.
		Repetitive nodes are labeled with their name, followed by their surname in parenthesis.
	}
	\label{figDiffSurname}
\end{figure}

\begin{figure}[h]
	\centering{%
		$\vcenter{\hbox{\includegraphics[width=0.4\textwidth]{images/hsptreeL}}}
		\xrightarrow[]{\text{prepend~} {\tt a}}
		\vcenter{\hbox{\includegraphics[width=0.4\textwidth]{images/hsptreeR}}}$
	}
	\caption{We take the text~$T$ of \Cref{figClassicESP} and build \hInst[T] (left) and \hInst[{\tt a} T] (right) like in \Cref{figClassicESPFragile}.
		The HSP does not change any edges of $\hInst[T]$, thanks to the usage of surnames.
	}
	\label{figDifferenceToESPT}
\end{figure}

The motivation of our modification will become apparent when examining the fragile nodes that are the last two nodes on a repeating meta-block.
Although they could still change their names when prepending characters to the text,
their surnames do not get changed by the parsing:
Focus on height $h$ in $\hInst[\textT]$, and look at
two meta-blocks $\espnode{\textT}_h[\nu]$ and $\espnode{\textT}_h[\mu]$ with $\iend{\nu} < \ibeg{\mu}$.
Assume that $\nu$ is a \Type{1} meta-block, and that $\mu$ is surrounded.
The nodes of $\nu$ are grouped in meta-blocks by \emph{surnames},
and the surnames of the fragile nodes belonging to repeating meta-blocks cannot change by prepending some string to the input.
So nodes contained in $\mu$ are stable (\Cref{figFragileStabled}).
Due to the way \Type{M} meta-blocks are created, the same is true when $\nu$ is a \Type{M} meta-block (compare \Cref{figMixed} with \Cref{figGoodMixed}).
Hence, the modification prevents a surrounded node from being changed severely, which is formalized as:

\begin{lemma}\label{lemmaSurroundedFragileHSP}
  If a surrounded node is neither stable nor semi-stable,
  it can only be changed to a node whose generated substring is a prefix of the generated substring of an already existing node.
\end{lemma}
\begin{proof}
There are two (non-exclusive) properties for a node to be fragile and surrounded:
It belongs to 
the last two nodes built on a repeating meta-block, or its subtree contains a fragile surrounded node.
Let $v$ be one of the \emph{lowest} surrounded fragile nodes.
Since $v$ cannot contain any fragile surrounded node, 
it is one of the last two nodes built on a repeating meta-block $\espnode{\textT}_h[\mu]$.
Moreover, $\espnode{\textT}_h[\ibeg{\mu}-3..\ibeg{\mu}-1]$ contains a fragile non-surrounded node.
But since $v$ is surrounded, the condition
  $\abs{\mu} \ge \lcontext \ge 8$ (for $n > 4$) holds; so there is a repetitive node~$u$ consisting of three nodes in $\mu$.
  Any node with the same surname (as $u$ or $v$) generates a substring that is a prefix of the generated substring of~$u$.
  The parsing of HSP trees assures that any surrounded node located to the right of $\espnode{\textT}_h[\mu]$ is stable.
  This situation carries over to higher layers until the number of nodes with the same surname gets shrunken below $8$,
  at which fragile nodes containing $v$ in their subtrees are not surrounded anymore.
  Therefore, the proof is done by recursively applying this analysis.
\end{proof}


\begin{figure}[t]
	\centerline{%
		\includegraphics[scale=1.0]{images/surnames}
}

\caption{Assume that ${\tt a}^{k} {\tt (ba)}^3$ is a prefix of $\textT_h$ on some height $h$.
	The parsing creates a repeating meta-block consisting of the characters ${\tt a}^k$, and a \Type{2} meta-block containing the characters ${\tt (ba)}^3$.
		For $k \ge 2$ it is impossible 
		to modify the latter meta-block by prepending characters (bottom figure),
		since the parsing always groups adjacent nodes with the same surname into one repeating meta-block.
%		Nodes higher than $h$ are depicted by a tuple consisting of its name (composed by commas) and an optional, semicolon-separated surname as its last entry.
	} 
\label{figFragileStabled}
\end{figure}


\begin{figure}[t]
	\centerline{%
		\includegraphics[scale=1.0]{images/mixed}
}
\caption{A \Type{M} meta-block is created by fusing a single character with its sibling meta-block.
	We choose the tie breaking rule to fuse the character with its \emph{right} meta-block.
	In order to see why this rule is advantageous, we temporarily modify the parsing to choose the \emph{left} meta-block, if applicable.
	Let us examine the trees of
	$\textT = a^{19}ba^5{(ba)}^3$ (top) and
	${\tt a} \textT$ (bottom).
	In both trees, the two rightmost blocks of the \Type{M} meta-block on the bottom level are children of the leftmost node
		of the right meta-block on the next level.
		Prepending a character to $\textT$ may change those bottom level nodes and therefore change the right meta-block on height~$2$.
	} 
\label{figMixed}
\end{figure}

\begin{figure}[t]
	\centerline{%
		\includegraphics[scale=1.0]{images/goodmixed}
}
\caption{%
	We apply HSP with our tie breaking rule defined in \Cref{secESP} to the strings $\textT$ (top) and ${\tt a} \textT$ (bottom) of \Cref{figMixed}.
	Only the fragile nodes of the leftmost meta-blocks on each height may differ.
	} 
	\label{figGoodMixed}
\end{figure}





\subsection{Sparse Suffix Sorting in Text Space}

The \intWort{truncated \hTree{}~(\thTree{})} is the truncated version of the \hTree{}.
It is defined analogously as the \teTree{} (see \Cref{secTSESPImpl}), with the exception of the surnames:
For each repetitive node, we mark whether its surname is the name of an upper node, of an $\eta$-node, or of a lower node.
Therefore, we need to save the names of certain lower nodes in the reverse dictionary of~$\dic$.
This is only necessary when an upper node or an $\eta$-node~$v$ has a surname that is the name of a lower node.
If~$v$ is an upper node having a surname equal to the name of a lower node, the $\eta$-nodes in the subtree rooted at~$v$ have the same surname, too.
So the number of lower node entries in the reverse dictionary is upper bounded by the number of $\eta$-nodes, 
and each lower node generates a substring of length less than $3^\eta$.
We conclude that the results of \Cref{lemmaBuildTSESP} and \Cref{lemmaTruncatedLCE} apply to the \thTree{}, too.

For proving \Cref{thmSparseSuffixSorting}, 
it remains unclear how the \thTree{}s are stored in text space, and how much the running time for an LCE query gets affected.
Considering the construction in text space, it is nontrivial to give an efficient solution 
for~\ref{ruleCreate} and~\ref{ruleMerge} in \Cref{secAbstAlgo}.
In the following, we will fix $\eta$ in \Cref{lemmaEta}, and develop \Cref{corTSESPTextSpace} to deal with~\ref{ruleCreate}, 
\Cref{corTSESPLCE} for the LCE queries,
and \Cref{lemmaConcatTSESP} for~\ref{ruleMerge}.


Assume that we want to store $\thInst[\substr{T}{\intervalI}]$ on some text interval $\intervalI$.
Since \thInst[\substr{T}{\intervalI}] could contain nodes with $\abs{\intervalI}$ %$\idsetsize{T[i..i+l-1]} \le 2l$ 
distinct names, 
it requires $\Oh{\abs{\intervalI}}$ words, i.e., $\Oh{\abs{\intervalI} \lg n}$ bits of space
that do not fit in the $\abs{\intervalI} \lg \sigma$~bits of $T[\intervalI]$.
Taking some constant $\alpha$ (independent of $n$ and $\sigma$, but dependent of the size of a single node),
we can solve this space issue by setting $\eta := \log_3 (\alpha \lg^2 n/\lg \sigma)$:

\begin{lemma}\label{lemmaEta}
	Let $\eta = \log_3 \tuple{\alpha \lg^2 n/\lg\sigma}$.
	Then the number of nodes is bounded by $\Oh{l (\lg\sigma)^{0.7} / (\lg n)^{1.2}}$. % = \Oh{l / \sqrt{\lg n}}$.
	An $\eta$-node generates a substring containing at most $\upgauss{\alpha (\lg n)^2 / (\lg\sigma)}$ characters.
\end{lemma}
\begin{proof}
	The generated substring of an $\eta$-node is at least $2^\eta$ long, and takes at least
\[
	2^{\eta} \lg\sigma 
= 3^{\eta} (2/3)^{\eta} \lg\sigma 
= \alpha (\alpha \lg^2 n / \lg\sigma)^{\log_3 2 - 1} \lg^2 n 
= (\alpha^{\log_3 2}) (\lg n)^{2 \log_3 2} (\lg \sigma)^{1-\log_3 2} 
\geq \alpha^{0.6} (\lg n)^{1.2} (\lg \sigma)^{0.3}
\]
bits, where we used that $\eta = \log_3(\alpha \lg^2 n / \lg\sigma) = (\log_3 2 - 1) \log_{2/3}(\alpha \lg^2 n / \lg\sigma)$.
So the number of nodes is bounded by $\numNodes{l} \le l \lg\sigma / (\alpha^{0.6} (\lg n)^{1.2} (\lg\sigma)^{0.3}) = \Oh{l (\lg\sigma)^{0.7} / (\lg n)^{1.2}}$.
\end{proof}

Applying \Cref{lemmaEta} to the results elaborated in \Cref{secTSESPImpl} for the \teTree{}s yields 
\begin{corollary}\label{corTSESPTextSpace}
	We can compute a \thTree{} on a substring of length~$l$ 
	in $\Oh{l \lg^*n + \lookupTime \numNodes{l} + l \lg\lg n }$~time.
	The tree takes $\Oh{\numNodes{l}}$ space. We need a working space of $\Oh{\lg^2 n \lg^*n / \lg \sigma}$ characters.
\end{corollary}
\begin{proof}
	We follow the proof of \Cref{lemmaBuildTSESP}.
	The tree has at most $\numNodes{l}$ nodes, and thus takes 
	$\Oh{\numNodes{l}}$ text space.
	Constructing an $\eta$-node uses $\Oh{3^\eta \lg^*n} = \Oh{\lg^2 n \lg^*n / \lg \sigma}$ characters as working space.
\end{proof}
\begin{corollary}\label{corTSESPLCE}
	An LCE query on two \thTree{}s can be answered in 
	$\Oh{\lg^*n \lg n}$ time.
\end{corollary}
\begin{proof}
	LCE queries are answered as in \Cref{lemmaTruncatedLCE}.
The value of $\eta$ is set so that $3^{\eta} \lg\sigma = \alpha \lg^2 n$ holds.
Since an $\eta$-node generates a substring comprising $\alpha \lg^2 n/\lg \sigma$ characters, we can check the subtree of an $\eta$-node by examining $\alpha \lg n$ words.
Overall, these additional costs are bounded by $\Oh{(\lcontext + \rcontext)\lg n}$ time, and do not worsen the running time 
$\Oh{ \lg^* n \tuple{\lg(n/2^\eta) + \alpha \lg n} } = \Oh{\lg^*n \lg n}$.
\end{proof}

We analyze the merging when applied by the sparse suffix sorting algorithm in \Cref{secAbstAlgo}. 
Assume that our algorithm found two intervals $[i..i+l-1]$ and $[j..j+l-1]$ with $T[i..i+l-1] = T[j..j+l-1]$.
Ideally, we want to construct \thInst[\substr{T}{i..i+l-1}] in the text space $[j..j+l-1]$,
leaving $T[i..i+l-1]$ untouched so that parts of this substring can be referenced by the $\eta$-nodes.
Unfortunately, there are two situations that make the life of a \thTree{} complicated:
\begin{itemize}
	\item the need for merging \thTree{}s, and
	\item possible overlapping of the intervals $[i..i+l-1]$ and $[j..j+l-1]$.
\end{itemize}

{\bf Partitioning of \LCEI{}s.}
In order to merge trees, we have to take special care of those $\eta$-nodes that are fragile, 
because their names may have to be recomputed during a merge.
In order to recompute the name of an $\eta$-node~$v$, consisting of a pointer and a length, 
we have to find a substring that consists of $v$'s generated substring and some adjacent characters with respect to the original substring in the text.
That is because the parsing may assign a new pointer and a new length to an $\eta$-node, possibly enlarging the generated substring, 
or letting the pointer refer to a different substring.
%Unfortunately, our representation of the name of an $\eta$-nodes prohibits the fragmentation of any generated substring.

The name for a surrounded fragile $\eta$-nodes $v$ is easily recomputable thanks to~\Cref{lemmaSurroundedFragileHSP}:
Since the new generated substring of $v$ is a prefix of the generated substring of an already existing $\eta$-node $w$,
which is found in the reverse dictionary for $\eta$-nodes,
we can create a new name for $v$ from the generated substring of $w$.

Unfortunately, the same approach does not work with the non-surrounded $\eta$-nodes.
Those nodes have a generated substring that is found on the border area of $T[j..j+l-1]$.
If we leave this area untouched, we can use it for creating names of a non-surrounded $\eta$-node during a reparsing.
Therefore, we mark those parts of the interval $[j..j+l-1]$ as read-only.
Conceptually, we partition an \LCEI{} into subintervals of green and red intervals (see~\Cref{figMargin});
we free the text of a \intWort{green interval} for overwriting, while prohibiting write-access on a \intWort{red interval}.
The green intervals are managed in a dynamic, global list.
We keep the invariant that
\begin{enumerate}[leftmargin=*,label={Invariant~\arabic*:},ref={Invariant~\arabic*}]
	\item $\margin := \upgauss{2 \alpha \lg^2 n \lcontext / \lg \sigma} = \Ot{g}$ positions
		of the left and right ends of each \LCEI{} are \emph{red}. \label{invRedInterval}
\end{enumerate}
This invariant solves the problem for the non-surrounded nodes.
%implies that we must leave the $\margin$ left- and $\margin$ rightmost positions of $[j..j+l-1]$ untouched.

  \begin{figure}[h]
  	\centering{%
		\includegraphics[scale=1.0]{images/margin}
  	}
	\caption{The border areas of each \LCEI{} are marked read-only such that we can reparse non-surrounded nodes and merge two trees. }
	\label{figMargin}
  \end{figure}

{\bf Allocating Space.}
We can store the upper part of the \thTree{} in a green interval, since
$\numNodes{l} \lg n \le l \alpha^{0.6} (\lg\sigma)^{0.7} / (\lg n)^{0.2} = \oh{l \lg \sigma}$ holds.
By choosing $\gap$ and $\alpha$ properly, 
we can always leave $\margin \lg \sigma /\lg n = \Oh{\lg^*n \lg n}$ words on a green interval untouched, sufficiently large for the working space needed by \Cref{corTSESPTextSpace}.
Therefore, we pre-compute $\alpha$ and $\gap$ based on the input $T$, and set both as \emph{global} constants.
Since the same amount of free space is needed during a later merging when reparsing an $\eta$-node, we add the invariant that
% Choosing $\gap$ sufficiently large guarantees us to have at least $\margin$ space left on a green interval after the computation.
% By setting $\alpha$ properly, we save space, 
% sufficiently enough to store the upper part of the \thTree{} in $T[\intervalI]$.
% %By choosing an appropriate $\alpha$, we will see that it is possible to store any merged trees in text space, too.
% We will assume that a working space of $\Oh{3^\eta \lg^* n \lg \sigma/\lg n}$ is granted for each operation such that 
% we can compute the $\eta$-nodes like in the proof of \Cref{lemmaBuildTSESP}.
% We will see that this working space is actually part of the text that we are going to overwrite.
\begin{enumerate}[leftmargin=*,label={Invariant~\arabic*:},ref={Invariant~\arabic*}]
		\setcounter{enumi}{1}
	\item each \LCEI{} has $\margin \lg \sigma /\lg n$ free space left on a green interval. \label{invWorkingSpace}
\end{enumerate}
For the merging, we need a more sophisticated approach that respects both invariants:

{\bf Merging.}
We introduce a merge operation that allows the merge of two \thTree{}s whose \LCEI{}s have a gap of less than $\gap$ characters.
The merge operation builds new $\eta$-nodes on the gap. 
The $\eta$-nodes whose generated substrings intersect with the gap are called \intWort{bridging} nodes.
%We call those nodes and the $\eta$-nodes on the out-most red-interval of both facing sides of the trees the \intWort{bridging} $\eta$-nodes.
The bridging nodes have the same problem as the non-surrounded $\eta$-nodes, since
the gap may be a unique substring of $T$.
%Each of these margins of length $\margin$ helps a bridging $\eta$-node to find its generated substring in the following, special situations:

Let $\intervalI$ and $\intervalJ$ be two \LCEI{}s with $0 \le \ibeg{\intervalJ} - \iend{\intervalI} \le \gap$, where on each interval a \thTree{} 
has been computed.
We compute $\thInst[\substr{T}{\ibeg{\intervalI}..\iend{\intervalJ}}]$ by merging both trees.
By \Cref{lemmaTreeCombine}, at most $\Oh{\lcontext+\rcontext}$ nodes at every height on each tree have to be reprocessed, 
and some bridging nodes connecting both trees have to be built.
Unfortunately, the text may not contain another occurrence of $T[\iend{\intervalI}-\margin..\ibeg{\intervalJ}+\margin]$ 
such that we could overwrite $T[\iend{\intervalI}-\margin..\ibeg{\intervalJ}+\margin]$.
Therefore, we mark this interval as red.
%Due to~\ref{invRedInterval}, the right end of $\intervalI$ and the left end of $\intervalJ$ are already marked red.
So we can use the characters contained in $T[\iend{\intervalI}-\margin..\ibeg{\intervalJ}+\margin]$ for 
creating the bridging $\eta$-nodes, and for modifying the non-surrounded nodes of both trees~(\Cref{figEspMerge}).
%We see in \Cref{lemmaConcatTSESP} how~\ref{invWorkingSpace} gets retained.
Since the gap consists of less than $\gap$ characters, 
the bridging nodes need at most $\Oh{\lg n \lg^* n}$ additional space.
By choosing $\gap$ and $\alpha$ sufficiently large, we can maintain~\ref{invWorkingSpace} for the merged \LCEI{}.

{\bf Interval Overlapping.}
Assume that the \LCEI{}s $[i..i+l-1]$ and $[j..j+l-1]$ overlap, \wlogg{} $j > i$.
Our goal is to create \thInst[\substr{T}{i..i+l-1}].
Since $T[i..i+l-1] = T[j..j+l-1]$, the substring $T[i..j+l-1]$ has a period $1 \le d \le j-i$, i.e.,
$T[i..j+l-1] = \textS^k \textT$, where $\abs{\textS} = d$ and $\textT$ is a prefix of $\textS$, for some $k \ge 2$.
First, we compute the smallest period $d \le j - i$ of $T[i..j+l-1]$ in $\Oh{l}$ time~\cite{Kolpakov:1999:FMR:795665.796470}.
By definition, each substring of $T[j+\margin..j+l-1]$ appears also $d$~characters earlier.
The substring $T[i..i+d+\margin-1]$ is used as a reference and therefore marked red.
Keeping the original characters in $T[i..i+d+\margin-1]$, we can restore the generated substrings of every $\eta$-node by an arithmetic progression:
Assume that the generated substring of an $\eta$-node is $T[b..e]$ with $i+d+\margin \le b < e \le j+l-1$.
Since $\abs{[b..e]} \le \margin$, we find a $k \ge 1$ such that $T[b..e] = T[[b-d^k..e-d^k]$ and $[b-d^k..e-d^k] \subseteq [i..i+d+\margin-1]$.
Hence, we can mark the interval~$[i+d+\margin..j+l-1-\margin]$ \emph{green}.
The partitioning into red and green intervals is illustrated in \Cref{figMergePeriod}.


  \begin{figure}[h]
  	\centering{%
		\includegraphics[scale=1.0]{images/truncatedmerge}
  	}
	\caption{The merging is performed only if the gap between both trees is less than $\gap$.
		The substring $T[\iend{\intervalI}-\margin..\ibeg{\intervalJ}+\margin]$ is marked red for the sake of the bridging nodes.
	}
	\label{figEspMerge}
  \end{figure}

  \begin{figure}[h]
  	\centering{%
		\includegraphics[scale=1.0]{images/mergeperiod}
  	}
	\caption{Assume $\intervalI = [\bar{p}..\bar{p}+l-1]$ and $\intervalJ = [\hat{p}..\hat{p}+l-1]$ are overlapping.
		$T[\intervalI\cup\intervalJ]$ has the smallest period~$d$. 
		To avoid the fragmentation of generated substrings, it is sufficient to make $\margin+d$ characters on the left read-only.
	}
	\label{figMergePeriod}
  \end{figure}

  Finally, the time bound for the above merging strategy is given by


\begin{corollary}\label{lemmaConcatTSESP}
	Given two \LCEI{}s $\intervalI$ and $\intervalJ$ 
	with $0 \le \ibeg{\intervalJ} - \iend{\intervalI} \le \gap$.
We can build \thInst[\substr{T}{\ibeg{\intervalI}..\iend{\intervalJ}}]
in $\Oh{\gap \lg^* n + \lookupTime\numNodes{\gap}  + \gap\eta\wordpack + \lookupTime \lg^*n \lg n}$ time.
  % and $\margin$ words of working text space.
\end{corollary}
\begin{proof}
	We simulate the algorithm of \Cref{lemmaTreeCombine} on a \thTree{}.
	By~\ref{invWorkingSpace} there is enough space left on a green interval 
	to recompute the nodes considered in the proof of \Cref{lemmaTreeCombine}, and to create the bridging nodes in fashion of \Cref{corTSESPTextSpace}.
	%	using a text space of size $\margin$ for creating the $\eta$-nodes.
	Both creating and recomputing takes overall 
$\Oh{\gap \lg^* n + \lookupTime\numNodes{\gap}  + \gap\eta\wordpack}$ time.
\end{proof}

%These three \namecrefs{lemmaConcatTSESP} prove that the \thTree{}s are a representation of the \DynLCE{} type.
There is one problem left before we can prove the main result of the paper:
The sparse suffix sorting algorithm of \Cref{secAbstAlgo} creates \LCEI{}s 
on substrings smaller than $\gap$ between two \LCEI{}s temporarily when applying~\ref{ruleCreate}.
We cannot afford to build such tiny \thTree{}s, since they cannot respect both invariants.
Since a temporarily created \DynLCE{} is eventually merged with a \DynLCE{} on a large \LCEI{}, 
we do not create a \thTree{} if it covers less than $\gap$ characters.
Instead, we apply the new merge operation of \Cref{lemmaConcatTSESP} directly, merging two trees that have a gap of less than $\gap$ characters.
With this and the other properties stated above, we come to 


\begin{proof}[Proof of \Cref{thmSparseSuffixSorting}]
	The analysis is split into suffix comparison, tree generation and tree merging:
	\begin{itemize}
		\item 
			Suffix comparison is done as in the proof of \Cref{thmAbstractExtraSpace}.
			LCE queries on \eTree{}s and \thTree{}s are conducted in the same time bounds (compare \Cref{lemmaLCE} with \Cref{corTSESPLCE}).
		\item 
			All positions considered for creating the \thTree{}s belong to $\Comlcp$.
			Constructing the \thTree{}s costs at most
			$\Oh{ \abs{\Comlcp} \lg^*n + \lookupTime\numNodes{\abs{\Comlcp}}  + \abs{\Comlcp} \lg \lg n}$ overall time, due to
			\Cref{corTSESPTextSpace}.
		\item 
			Merging in the fashion of \Cref{lemmaConcatTSESP} does not affect the overall time:
			Since a merge of two trees introduces less than $\gap$ new text positions to an \LCEI{},
			we follow by the proof of \Cref{thmExtraSpace} that the time for merging is upper bounded by the construction time.
			% Let $\delta$ be the number of \LCEI{}s.
			% Since each \thTree{} covers at least $\gap$ characters, 
			% and a merge of two trees introduces less than $\gap$ new text positions to an \LCEI{},
			% the running time for merging is bounded by the time for creating the trees.
			% Therefore, $\delta \gap = \Oh{\abs{\Comlcp}}$ holds, and we get
			% $\Oh{\delta \lookupTime \lg^*n \lg n} = \Oh{\abs{\Comlcp} \lookupTime}$.
	\end{itemize}
	By \Cref{thmAbstractExtraSpace}, the time for generating and merging the trees is bounded by
	\[
		\Oh{\abs{\Comlcp} \lg^* n + \lookupTime\numNodes{\abs{\Comlcp}}  + \abs{\Comlcp} \lg\lg n } =
		\Oh{\abs{\Comlcp} \tuple{\lookupTime (\lg \sigma)^{0.7} / (\lg n)^{1.2} + \lg\lg n }  } =
%		\Oh{\abs{\Comlcp} \tuple{(\lg \sigma)^{0.7} / (\lg n)^{0.2}} + \lg\lg n} = 
                \Oh{\abs{\Comlcp} \sqrt{\lg n} },
	\]
	since $\lookupTime \in \Oh{\lg n}$.
	The time for searching and sorting is 
	\(
		\Oh{ m \lg m \lg^* n \lg n}
	\).
	The external data structures used are $\SAVL(\Suf(\Pos))$ and the search tree for the \LCEI{}s, each taking $\Oh{m}$ space.
\end{proof}



\bibliographystyle{abbrvnat}
\bibliography{refs}

\end{document}
\appendix


\section{LCE and truncation on HSP trees}
The representation of an HSP tree stores additionally the surname and the exponent of every repetitive node.
The \intWort{exponent} of a repetitive node $v$ is the length of the node-string $N$ occupied by $v$ that consists of nodes whose names are identical to $v$'s surname.

We can perform LCE queries with the HSP tree like in \Cref{lemmaLCE}.
When encountering repetitive nodes, the query algorithm is actually simpler as for ESP trees, 
as we can use the exponent to compare repetitive nodes (even if the nodes are fragile or non-surrounded).
In more detail, assume two repetitive nodes $u$ and $v$ having the surnames $n_u$ and $n_v$. 
Let $n_u$ and $n_v$ be the names used in the node strings $N_u$ and $N_v$ that are occupied by $u$ and $v$, respectively.
The exponent of $u$ and $v$ are given by $\abs{N_u}$ and $\abs{N_v}$, respectively.
If $n_u \not= n_v$, then all nodes of $N_u$ and $N_v$ are different.
Otherwise, every node of $N_u$ and $N_v$ spans the same subtree.
If we assume that $\abs{N_u} \le \abs{N_v}$, then the generated substring of $u$ is a prefix of the generated substring of $v$.
So instead of testing the equality of both nodes (involving the exploration of both subtrees in case of inequality), 
we note the difference in the exponents, and take the next two nodes (during climbing up or walking down).

\begin{proof}[Proof of \Cref{lemmaStableSolidHSP}]
	We modify the proof of \Cref{lemmaStableSolid}~(\ref{itemStableSolid}) at the point where we conclude that $\nu$ has to be repeating.
  By our modification of the ESP algorithm,
  the surname of every node in $\espnode{\textT}_{h}[i_v..j_v]$ is different from its previous and next sibling.
\end{proof}


main.bbl
\begin{thebibliography}{14}
\providecommand{\natexlab}[1]{#1}
\providecommand{\url}[1]{\texttt{#1}}
\expandafter\ifx\csname urlstyle\endcsname\relax
  \providecommand{\doi}[1]{doi: #1}\else
  \providecommand{\doi}{doi: \begingroup \urlstyle{rm}\Url}\fi

\bibitem[Andersson and Nilsson(1994)]{forwardradixsort}
A.~Andersson and S.~Nilsson.
\newblock A new efficient radix sort.
\newblock In \emph{Foundations of Computer Science, 35th Annual Symposium on},
  pages 714--721, 1994.

\bibitem[Bille et~al.(2012)Bille, Gørtz, Sach, and Vildhøj]{billeLCEPre}
P.~Bille, I.~Gørtz, B.~Sach, and H.~Vildhøj.
\newblock Time-space trade-offs for longest common extensions.
\newblock In J.~Kärkkäinen and J.~Stoye, editors, \emph{Combinatorial Pattern
  Matching}, volume 7354 of \emph{Lecture Notes in Computer Science}, pages
  293--305. Springer, 2012.
\newblock ISBN 978-3-642-31264-9.

\bibitem[Bille et~al.(2013)Bille, Fischer, G{\o}rtz, Kopelowitz, Sach, and
  Vildh{\o}j]{BFGKSV13}
P.~Bille, J.~Fischer, I.~L. G{\o}rtz, T.~Kopelowitz, B.~Sach, and H.~W.
  Vildh{\o}j.
\newblock Sparse suffix tree construction in small space.
\newblock In \emph{Proc. ICALP}, volume 7965 of \emph{LNCS}, pages 148--159,
  2013.

\bibitem[Bille et~al.(2015)Bille, Gørtz, Knudsen, Lewenstein, and
  Vildhøj]{billeLCE}
P.~Bille, I.~Gørtz, M.~Knudsen, M.~Lewenstein, and H.~Vildhøj.
\newblock Longest common extensions in sublinear space.
\newblock In \emph{Combinatorial Pattern Matching}, volume 9133 of
  \emph{Lecture Notes in Computer Science}, pages 65--76. Springer
  International Publishing, 2015.
\newblock ISBN 978-3-319-19928-3.

\bibitem[Cormode and Muthukrishnan(2007)]{Cormode2007sed}
G.~Cormode and S.~Muthukrishnan.
\newblock The string edit distance matching problem with moves.
\newblock \emph{ACM Transactions on Algorithms}, 3\penalty0 (1), 2007.

\bibitem[Ferragina and Fischer(2007)]{ferragina07suffix}
P.~Ferragina and J.~Fischer.
\newblock Suffix arrays on words.
\newblock In \emph{Proc.\ CPM}, volume 4580 of \emph{LNCS}, pages 328--339.
  Springer, 2007.

\bibitem[Franceschini and Grossi(2004)]{betterSearching}
G.~Franceschini and R.~Grossi.
\newblock No sorting? better searching! [optimal array organization].
\newblock In \emph{Foundations of Computer Science, 2004. Proceedings. 45th
  Annual IEEE Symposium on}, pages 491--498, Oct 2004.
\newblock \doi{10.1109/FOCS.2004.43}.

\bibitem[I et~al.(2014)I, K{\"a}rkk{\"a}inen, and Kempa]{I2014FSS}
T.~I, J.~K{\"a}rkk{\"a}inen, and D.~Kempa.
\newblock Faster sparse suffix sorting.
\newblock In \emph{STACS}, pages 386--396, 2014.

\bibitem[Irving and Love(2003)]{Irving2003sbs}
R.~W. Irving and L.~Love.
\newblock The suffix binary search tree and suffix {AVL} tree.
\newblock \emph{J. Discrete Algorithms}, 1\penalty0 (5-6):\penalty0 387--408,
  2003.

\bibitem[K{\"a}rkk{\"a}inen et~al.(2006)K{\"a}rkk{\"a}inen, Sanders, and
  Burkhardt]{ksb2006}
J.~K{\"a}rkk{\"a}inen, P.~Sanders, and S.~Burkhardt.
\newblock Linear work suffix array construction.
\newblock \emph{J. ACM}, 53\penalty0 (6):\penalty0 918--936, 2006.

\bibitem[Kolpakov and Kucherov(1999)]{Kolpakov:1999:FMR:795665.796470}
R.~Kolpakov and G.~Kucherov.
\newblock Finding maximal repetitions in a word in linear time.
\newblock In \emph{Proceedings of the 40th Annual Symposium on Foundations of
  Computer Science}, FOCS '99, pages 596--, Washington, DC, USA, 1999. IEEE
  Computer Society.
\newblock ISBN 0-7695-0409-4.

\bibitem[Nong et~al.(2011)Nong, Zhang, and Chan]{nong11two}
G.~Nong, S.~Zhang, and W.~H. Chan.
\newblock Two efficient algorithms for linear time suffix array construction.
\newblock \emph{IEEE Trans. Computers}, 60\penalty0 (10):\penalty0 1471--1484,
  2011.

\bibitem[Puglisi et~al.(2007)Puglisi, Smyth, and Turpin]{puglisi07taxonomy}
S.~J. Puglisi, W.~F. Smyth, and A.~Turpin.
\newblock A taxonomy of suffix array construction algorithms.
\newblock \emph{ACM Comput.\ Surv.}, 39\penalty0 (2), 2007.

\bibitem[Sedgewick and Wayne(2011)]{sedgewickAlgorithms}
R.~Sedgewick and K.~Wayne.
\newblock \emph{{Algorithms}}.
\newblock Addison-Wesley, 2011.
\newblock ISBN 978-0-321-57351-3.

\end{thebibliography}
