4 papers
Linear Time Runs over General Ordered Alphabets
Jonas Ellert, Johannes Fischer
A run in a string is a maximal periodic substring. For example, the string contains the runs and $\texttt{ee} = \texttt…
LCP-Aware Parallel String Sorting
Jonas Ellert, Johannes Fischer, Nodari Sitchinava
When lexicographically sorting strings, it is not always necessary to inspect all symbols. For example, the lexicographical rank of "europar" amongst the strings "eureka", "eurasia…
Space Efficient Construction of Lyndon Arrays in Linear Time
Philip Bille, Jonas Ellert, Johannes Fischer +4
We present the first linear time algorithm to construct the -bit version of the Lyndon array for a string of length using only bits of working space. A simpler varia…
Bidirectional Text Compression in External Memory
Patrick Dinklage, Jonas Ellert, Johannes Fischer +2
Bidirectional compression algorithms work by substituting repeated substrings by references that, unlike in the famous LZ77-scheme, can point to either direction. We present such a…