Simple Linear-Time Repetition Factorization
摘要
A factorization \(f_1, \ldots , f_m\) of a string w of length n is called a repetition factorization of w if \(f_i\) is a repetition, i.e., \(f_i\) is a form of \(x^kx'\) where x is a non-empty string, \(x'\) is a (possibly-empty) proper prefix of x, and \(k \ge 2\) . Dumitran et al. [SPIRE 2015] presented an O(n)-time and space algorithm for computing an arbitrary repetition factorization of a given string of length n. Their algorithm heavily relies on the Union-Find data structure on trees proposed by Gabow and Tarjan [JCSS 1985] that works in linear time on the word RAM model, and an interval stabbing data structure of Schmidt [ISAAC 2009]. In this paper, we explore more combinatorial insights into the problem, and present a simple algorithm to compute an arbitrary repetition factorization of a given string of length n in O(n) time, without relying on data structures for Union-Find and interval stabbing. Our algorithm follows the approach by Inoue et al. [ToCS 2022] that computes the smallest/largest repetition factorization in \(O(n \log n)\) time.