Text Indexing: From Reporting to Counting
2026-07-27 • Data Structures and Algorithms
Data Structures and Algorithms
AI summaryⓘ
The authors prove a simple but useful fact about trees: in any rooted tree with a certain number of leaves, there are only so many nodes whose depth is less than the number of leaves beneath them. Using this fact on a special tree built from a string, they show that the number of substrings appearing more frequently than their length is limited. This insight helps design data structures that efficiently count how often patterns appear in strings by precomputing counts for frequent substrings and using existing methods for the rest. Their approach improves query speed without using extra space, and they demonstrate its use in various string-related problems.
rooted treeleaf descendantssuffix triesubstring occurrencespreprocessingstring indexingpattern countingquery complexitydata structuresalgorithmic framework
Authors
Ben Bals, Panagiotis Charalampopoulos, Oded Lachish, Solon P. Pissis, Hilde Verbeek
Abstract
We prove an elementary yet powerful combinatorial lemma: in any rooted tree with $L$ leaves, the number of nodes whose depth is smaller than the number of their leaf descendants is at most $L$. For any string $T$ of length $n$, a direct application of this lemma to the suffix trie of $T$ yields that the number of substrings of $T$ whose length is smaller than their number of occurrences in $T$ is at most $n$. This combinatorial insight leads to space-efficient data structures with optimal query times for string counting problems via the following algorithmic framework: store the counts for the at most $n$ ``frequent'' substrings of $T$ in a preprocessing step, and use a reporting query to count for the ``infrequent'' substrings. Our framework acts as a convenient black box, lifting indexes with reporting time $\mathcal{O}(|P|+|\textsf{Occ}_T(P)|)$ to support counting queries in time $\mathcal{O}(|P|)$, where $P$ is the queried pattern and $\textsf{Occ}_T(P)$ is the set of occurrences of $P$ in $T$. As applications, we show efficient indexes for consecutive occurrences, weighted sequences, strings with utilities, and non-overlapping occurrences.