2026/07/27 by Ben Bals, Panagiotis Charalampopoulos, Oded Lachish +2
Computer Science · #cs.DS
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 O(|P|+|\textsfOccT(P)|) to support counting queries in time O(|P|), where P is the queried pattern and \textsfOccT(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.