2014/03/05 by Philip Bille, Bille, Philip, Patrick Hagge Cording +3
Computer Science · #Algorithms and Data Compression #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Natural Language Processing Techniques #Network Packet Processing and Optimization
paper · pdf · doi:10.48550/arxiv.1403.1065
openalex publication_date 2014/03/05 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We present a new algorithm for subsequence matching in grammar compressed strings. Given a grammar of size n compressing a string of size N and a pattern string of size m over an alphabet of size σ, our algorithm uses O(n+(nσ)/(w)) space and O(n+(nσ)/(w)+mlog Nlog w⋅ occ) or O(n+(nσ)/(w)log w+mlog N⋅ occ) time. Here w is the word size and occ is the number of occurrences of the pattern. Our algorithm uses less space than previous algorithms and is also faster for occ=o((n)/(log N)) occurrences. The algorithm uses a new data structure that allows us to efficiently find the next occurrence of a given character after a given position in a compressed string. This data structure in turn is based on a new data structure for the tree color problem, where the node colors are packed in bit strings.