19 citations · 65 across the 15 of their papers we have counts for
4 papers · 1 filter
Deterministic Sparse Suffix Sorting in the Restore Model
Johannes Fischer, Tomohiro I, Dominik Köppl
Given a text of length , we propose a deterministic online algorithm computing the sparse suffix array and the sparse longest common prefix array of in $O(c \sqrt{\lg n}…
Lempel Ziv Computation In Small Space (LZ-CISS)
Johannes Fischer, Tomohiro I, Dominik Köppl
For both the Lempel Ziv 77- and 78-factorization we propose algorithms generating the respective factorization using bits (for any positive constant …
Approximating LZ77 via Small-Space Multiple-Pattern Matching
Johannes Fischer, Travis Gagie, Paweł Gawrychowski +1
We generalize Karp-Rabin string matching to handle multiple patterns in time and space, where is the length of the text and is…
Beyond the Runs Theorem
Johannes Fischer, Štěpán Holub, Tomohiro I +1
Recently, a short and elegant proof was presented showing that a binary word of length contains at most runs. Here we show, using the same technique and a computer search…