Florian Kurpicz

Longest Common Extensions

We present practical implementations of two different approaches for space efficient data structures that can be used to answer longest common extension queries. The first approach is based on Rabin-Karp fingerprints and the second approach uses string synchronizing sets. It is interesting to see that, despite being a very naive algorithm, scanning is still one of the fastest ways to answer longest common extension queries. However, our longest common extension data structure based on string synchronizing sets is faster, but requires a small memory overhead of 10%-20% of the input size.

Implementations

Our implementations are available from the original repository and my fork that sometimes is ahead of the development compared to the original repository.

Posts Related to Longest Common Extensions

Video Presentation at ESA 2020
2020-08-31

Video Recording and Slides of our Paper @ ESA'20 are Online
Paper Accepted at ESA 2020
2020-06-18

Practical Performance of Space Efficient Data Structures for LCEs