A new characterization of maximal repetitions by Lyndon trees
Hideo Bannai, I Tomohiro, Shunsuke Inenaga, Yuto Nakashima, Takeda Masayuki, Kazuya Tsuruta · IEICE Technical Report; IEICE Tech. Rep. · 2014
We give a new characterization of maximal repetitions (or runs) in strings, using a tree defined on recursive standard factorizations of Lyndon words, called the Lyndon tree. The characterization leads to a remarkably simple novel proof of the linearity of the maximum number of runs ρ(n) in a string of length n. Furthermore, we show an upper bound of ρ(n)