STRUCTURAL FACTORIZATION OF SQUARES IN STRINGS

Abstract

A balanced double square in a string x consists of two squares starting in the same position and of comparable lengths. We present a unique fac- torization of the longer square into primitive components refereed to as the canonical factorization and analyze its properties. In particular, we examine the inversion factors and the right and left inversion subfactors. All three substrings are collectively referred to as rare factors as they occur only twice in a signi cant portion of the larger square. The inversion factors were es- sential for determining the classi cation of mutual con gurations of double squares and thus providing the best-to-date upper bound of 11n=6 for the number of distinct squares in a string of length n by Deza, Franek, and Thierry. The right and left inversion subfactors have the advantage of being half the length of the inversion factors, thus providing a stronger dis- crimination property for a possible third square. This part of the thesis was published by Bai, Franek, and Smyth. The canonical factorization and the right and left inversion subfactors are used to formulate and prove a signi cantly stronger version of the New Periodicity Lemma by Fan, Puglisi, Smyth, and Turpin, 2006, that basically restricts what kind of a third square can exists in a balanced double square. This part of the thesis was published by Bai, Franek, and Smyth. The canonical factorization and the inversion factors are applied to for- mulate and prove a stronger version of the Three Squares Lemma by Crochemore and Rytter. This part of the thesis was published by Bai, Deza, and Franek.