Abstract

We describe the first self-indexes able to count and locate pattern occurrences in optimal time within a space bounded by the size of the most popular dictionary compressors. To achieve this result, we combine several recent findings, including string attractors-new combinatorial objects encompassing most known compressibility measures for highly repetitive texts-and grammars based on locally consistent parsing.