Fully-Functional Suffix Trees and Optimal Text Searching in BWT-runs Bounded Space 2: A Text Whose BWT Has r Runs Has at Most 2rs Distinct Substrings of Length sResearch Paper
A text index answers questions about occurrences of a pattern without scanning the whole text. One reason to compress such an index is that many stored texts are repetitive: multiple versions of a document or genome often share long passages. The Burrows–Wheeler transform (BWT) rearranges a text's symbols in a way that groups related contexts. A small…