11 citations · 11 across the 1 of their papers we have counts for
3 papers
cs.DS2019
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…
cs.DS2017★ 11 cited
Dismantling DivSufSort
Johannes Fischer, Florian Kurpicz
We give the first concise description of the fastest known suffix sorting algorithm in main memory, the DivSufSort by Yuta Mori. We then present an extension that also computes the…
cs.DS2016
On the Benefit of Merging Suffix Array Intervals for Parallel Pattern Matching
Johannes Fischer, Dominik Köppl, Florian Kurpicz
We present parallel algorithms for exact and approximate pattern matching with suffix arrays, using a CREW-PRAM with processors. Given a static text of length , we first sho…