Fully-Functional Suffix Trees and Optimal Text Searching in BWT-runs Bounded Space 1: SA[p ± 1] Is Recovered From the Sample at the Phrase Start Preceding SA[p] − 1Research Paper
Collections of genomes, versioned documents and source-code histories are highly repetitive: most of each new item is a copy of something already stored. Full-text indexes such as the suffix array and the FM-index answer pattern queries on such collections, but their size grows with the text length , not with the amount of distinct content. The number of…