Prague Stringology Conference 2014

Haoyue Bai, Frantisek Franek and William F. Smyth

Two Squares Canonical Factorization

We present a new combinatorial structure in a string: a canonical factorization for any two squares that occur at the same position and satisfy some size restrictions. We believe that this canonical factorization will have application to related problems such as the New Periodicity Lemma, Crochemore-Rytter Three Squares Lemma, and ultimately the maximum-number-of-runs conjecture.

Download paper: Article in PostScript Article in PDF BibTeX Reference
 PostScript   PDF   BibTeX reference 
Download presentation: Presentation