Showing 2026Show all
3 papers · 1 filter
cs.DS2026
Practical and Space-Efficient LZ77 and LZ Pre-Compression via String Synchronizing Sets
Jonas Ellert, Lukas Nalbach
The Lempel-Ziv (LZ77) factorization decomposes a text into the least possible number of phrases that each refer to an earlier occurrence. It is this phrase count, rather than t…
cs.DS2026
Time-Optimal Construction of String Synchronizing Sets
Jonas Ellert, Tomasz Kociumaka
A key principle in string processing is local consistency: using short contexts to handle matching fragments of a string consistently. String synchronizing sets [Kempa, Kociumaka;…
cs.DS2026
Approximate Cartesian Tree Matching with Substitutions
Panagiotis Charalampopoulos, Jonas Ellert, Manal Mohamed
The Cartesian tree of a sequence captures the relative order of the sequence's elements. In recent years, Cartesian tree matching has attracted considerable attention, particularly…