Fingerprints in compressed strings

DOI10.1016/j.jcss.2017.01.002zbMath1370.68060arXiv1305.2777WikidataQ60554414 ScholiaQ60554414MaRDI QIDQ2396828

Patrick Hagge Cording, Inge Li Gørtz, Philip Bille, Hjalte Wedel Vildhøj, Søren Vind, Benjamin Sach

Publication date: 26 May 2017

Published in: Journal of Computer and System Sciences, Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1305.2777

zbMATH Keywords

longest common extensions; grammar-compressed string; Karp-Rabin fingerprints

Mathematics Subject Classification ID

68P30: Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science)

68Q42: Grammars and rewriting systems

68P05: Data structures

68W32: Algorithms on strings

Related Items

Small-space LCE data structure with constant-time queries, Practical Performance of Space Efficient Data Structures for Longest Common Extensions., Balancing run-length straight-line programs, Balancing straight-line programs for strings and trees, Finger search in grammar-compressed strings, Access, Rank, and Select in Grammar-compressed Strings

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The level ancestor problem simplified
• Bounded ordered dictionaries in O(log log N) time and O(n) space
• Surpassing the information theoretic bound with fusion trees
• Finding level-ancestors in trees
• String matching in Lempel-Ziv compressed strings
• Application of Lempel-Ziv factorization to the approximation of grammar-based compression.
• Log-logarithmic worst-case range queries are possible in space theta(N)
• A Faster Grammar-Based Self-index
• Time-Space Trade-Offs for Longest Common Extensions
• The string edit distance matching problem with moves
• Self-Indexed Grammar-Based Compression
• Fast Algorithms for Finding Nearest Common Ancestors
• Compactly encoding unstructured inputs with differential compression
• Dynamic ordered sets with exponential search trees
• The Smallest Grammar Problem
• Efficient algorithms for substring near neighbor problem
• Efficient randomized pattern-matching algorithms
• Design and implementation of an efficient priority queue
• A universal algorithm for sequential data compression
• Compression of individual sequences via variable-rate coding
• Faster Suffix Tree Construction with Missing Suffix Links
• Fully Dynamic Data Structure for LCE Queries in Compressed Space
• Finger Search in Grammar-Compressed Strings
• Longest Common Extensions with Recompression.
• Exact and Approximate Pattern Matching in the Streaming Model