Tomasz Kociumaka

Efficient Ranking of Lyndon Words and Decoding Lexicographically Minimal de Bruijn Sequence

2015 · arXiv (Cornell University)

We give efficient algorithms for ranking Lyndon words of length $n$ over an alphabet of size $σ$. The rank of a Lyndon word is its position in the sequence of lexicographically ordered Lyndon words of …

How Compression and Approximation Affect Efficiency in String Distance Measures

2022 · Society for Industrial and Applied Mathematics eBooks

Real-world data often comes in compressed form. Analyzing compressed data directly (without first decompressing it) can save space and time by orders of magnitude. In this work, we focus on fundamental sequence comparison problems and …