Locally Consistent Parsing for Text Indexing in Small Space

DOI10.1137/1.9781611975994.37MaRDI QIDQ5146805zbMATH OpenOpenAlexFDO

Authors Or Birenzwige, Shay Golan, Ely Porat

Publication date 2 February 2021

Published in Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Cited in

(17)

• Extracting the sparse longest common prefix array from the suffix binary search tree
• Internal shortest absent word queries in constant time and linear space
• Quasi-Linear-Time Algorithm for Longest Common Circular Factor
• Practical Performance of Space Efficient Data Structures for Longest Common Extensions.
• Near-optimal search time in -optimal space, and vice versa
• Near-optimal search time in -optimal space
• Near-optimal quantum algorithms for string problems
• Locally consistent decomposition of strings with applications to edit distance sketching
• Sparse suffix and LCP array: simple, direct, small, and fast
• Internal pattern matching queries in a text and applications
• Construction of sparse suffix trees and LCE indexes in optimal time and space
• Internal pattern matching in small space and applications
• Substring complexity in sublinear space
• Longest common extensions with wildcards: trade-off and applications
• Sparse suffix and LCP array: simple, direct, small, and fast
• Covers in optimal space
• Strictly in-place algorithms for permuting and inverting permutations

This page was built for publication: Locally Consistent Parsing for Text Indexing in Small Space

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5146805)