19 citations · 65 across the 15 of their papers we have counts for
25 papers
Average-Case Optimal Encodings and Efficient Worst-Case Indices for Element Distinctness Queries
Philip Bille, Johannes Fischer, Inge Li Gørtz +1
We study the data structure version of the \emph{element distinctness problem}: preprocess an array of elements from an alphabet of size to answer \textsc{All-Distinct} que…
Sliding Window String Indexing in Streams
Philip Bille, Johannes Fischer, Inge Li Gørtz +2
Given a string over an alphabet , the 'string indexing problem' is to preprocess to subsequently support efficient pattern matching queries, i.e., given a pattern string…
Engineering Predecessor Data Structures for Dynamic Integer Sets
Patrick Dinklage, Johannes Fischer, Alexander Herlez
We present highly optimized data structures for the dynamic predecessor problem, where the task is to maintain a set of -bit numbers under insertions, deletions, and predece…
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…