Simple Linear-Time Repetition Factorization

A factorization f₁,…,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≥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(nlogn) time.