Efficiently computing runs on a trie

Abstract

A maximal repetition, or run, in a string, is a maximal periodic substring whose smallest period is at most half the length of the substring. In this paper, we consider runs that correspond to a path on a trie, or in other words, on a rooted edge-labeled tree where the endpoints of the path must be a descendant/ancestor of the other. For a trie with $n$ edges, we show that the number of runs is less than $n$. We also show an asymptotic lower bound on the maximum density of runs in tries: ${\lim }_{n\to \infty }{\rho }_{\mathcal{T}}(n)/n\ge 0.993238$ where ${\rho }_{\mathcal{T}}(n)$ is the maximum number of runs in a trie with $n$ edges. Furthermore, we also show an $O(n\log \log n)$ time and $O(n)$ space algorithm for finding all runs.

an updated version of CPM 2019 paper (10.4230/LIPIcs.CPM.2019.23), submitted to a journal

References in corpus (2)

• The "Runs" Theorem
• New Lower Bounds for the Maximum Number of Runs in a String