Text Indexing and Searching in Sublinear Time

2017/12/20 by J. Ian Munro, Gonzalo Navarro, Munro, J. Ian +3 · 1 citation
Computer Science · #Algorithms and Data Compression #Cellular Automata and Applications #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #semigroups and automata theory

paper · pdf · doi:10.48550/arxiv.1712.07431

openalex publication_date 2017/12/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We introduce the first index that can be built in o(n) time for a text of length n, and can also be queried in o(q) time for a pattern of length q. On an alphabet of size σ, our index uses O(n√(log nlogσ)) bits, is built in O(n((loglog n)²+√(logσ))/√(log_σn)) deterministic time, and computes the number occ of occurrences of the pattern in time O(q/log_σn+log n). Each such occurrence can then be found in O(√(log nlogσ)) time. By slightly increasing the space and construction time, to O(n(√(log nlogσ)+ logσlog^ε n)) and O(nlog^3/2σ/log^1/2-ε n), respectively, for any constant 0

Citations

• Suffix Arrays: A New Method for On-Line String Searches

Cited by

• Counting Distinct Square Substrings in Sublinear Time

Related

• Optimal-Time Dictionary-Compressed Indexes
• String Indexing for Patterns with Wildcards
• Fast Compressed Self-Indexes with Deterministic Linear-Time Construction
• Full-fledged Real-Time Indexing for Constant Size Alphabets
• Optimal-Time Text Indexing in BWT-runs Bounded Space