String Powers in Trees

Abstract

In this paper we consider substrings of an unrooted edge-labeled tree, which are defined as the composite labels of simple paths. We study how the number of distinct repetitive substrings depends on their exponent $\alpha$. An $\alpha$-power is defined as a string U with an (integral, not necessarily shortest) period $|U|/\alpha$. For example, squares are 2-powers and cubes are 3-powers. We investigate the asymptotic growth of the maximal number $\mbox{powers}\alpha(n)$ofdistinct$\alpha$-powersoccurringassubstringsofatreewith$n$nodes.Themaximumnumberofsuchpowersbehavesmuchunlikeinstrings.Inapreviouswork(CPM2012.LNCS,vol7354.Springer,Berlin,pp27–40,2012.Itwasprovedthatthenumberofdifferentsquaresinatreeis$\mbox{powers}2(n)=\Theta(n^{4/3})$.Weextendthisresultandanalyzepowersofarbitraryrationalexponent$\alpha\ge 1$.Weidentifytwophase-transitionthresholds:1.$\mbox{powers}\alpha(n)=\Theta(n^2)$for$\alpha<2$;2.$\mbox{powers}\alpha(n)=\Theta(n^{4/3})$for$2\le \alpha<3$;3.$\mbox{powers}_\alpha(n)=O(n\log n)$for$\alpha>3$;ThisisafullversionofapaperpresentedatCPM2015.LNCS,vol9133.Springer,Berlin,pp284–294,2015.Comparedtotheearlierversion,weimproveourmaintechnicalcontribution,i.e.,theupperboundonthenumberofcubesinatree,from$O(n\log n)$to$O(n)$.Thisletsusobtainatightasymptoticcharacterizationofthe$\mbox{powers}$ function.