Counting Distinct Square Substrings in Sublinear Time

We consider a problem of counting distinct squares (and more generally, powers) in a string. Such problems are important not only from a purely theoretical point of view, but are also relevant in some applications in bioinformatics (see the book [27]). Strings of the form $X^2=XX$, for a non-empty string $X$, called squares (or tandem repeats), are the most natural type of repetition.

A fundamental algorithmic problem related to squares is checking if a given string of length $n$ is square-free, that is, if it avoids square substrings. Thue’s construction of an infinite ternary square-free string [44] can be viewed as the beginning of combinatorics on words. The first $𝒪(n\log n)$-time algorithm for checking square-freeness was given by Main and Lorentz [40]. An $𝒪(n)$-time algorithm for this problem, for the case of a constant-sized alphabet, was proposed by Crochemore [18]. Subsequently, $𝒪(n)$-time algorithms for square-freeness over an integer alphabet and over a general ordered alphabet follow from Kolpakov and Kucherov’s [36] and Ellert and Fischer’s [23] algorithms for computing runs under these assumptions, respectively. Most recently, Ellert, Gawrychowski, and Gourdel [24] obtained an $𝒪(n\log \sigma )$-time algorithm for testing square-freeness of a string over a general unordered alphabet of size $\sigma$; they also showed that the algorithm is optimal under these assumptions. Square-freeness was also studied in on-line [29, 37], parallel [2, 3, 20] and dynamic [1] settings.

A much more challenging problem than testing square-freeness, that has received significant attention, is computing the number of distinct square substrings of a given string. Fraenkel and Simpson were the first to show that a string of length $n$ contains $𝒪(n)$ dictinct squares [26]. Brlek and Li very recently, using arguments from linear algebra and graph theory, improved the $2n$ upper bound of Fraenkel and Simpson to just $n$; see [11, 10].

Linear-time algorithms for counting distinct square substrings were proposed by Gusfield and Stoye [28], Crochemore et al. [19], Bannai, Inenaga, and Köppl [6], and Charalampopoulos et al. [14]; notably, the last three results work for a string over an integer (generally, linearly sortable) alphabet. As already mentioned, testing square-freeness is a simpler problem than counting distinct squares. In particular, for a general (ordered) alphabet, element distinctness can be reduced in linear time to counting squares¹¹1As for the reduction, a sequence $a_1,\mathrm{\dots },a_n$ contains a repeating element, if and only if, string $a_1^2{b}_1{a}_2^2{b}_2\mathrm{\cdots }{a}_n^2{b}_n$, for a square-free string $b_1{b}_2\mathrm{\dots }{b}_n$ (say, a prefix of the infinite ternary square free string [44]), contains less than $n$ distinct square substrings., and the latter problem is hard: it requires $\mathrm{\Omega }(n\log n)$ time in the comparison model [8].

In the word-RAM model of computation with word size $\mathrm{\Theta }(\log n)$, we may store up to $\mathrm{\Omega }({\log }_{\sigma }n)$ string characters in a single machine word, where $\sigma$ is the size of the alphabet. The packed representation of a length-$n$ string $S$ over an integer alphabet $[0..\sigma )$ is a sequence of $𝒪(n/{\log }_{\sigma }n)$ integers, each encoding a fragment of $S$ of length $𝒪({\log }_{\sigma }n)$.

A recent line of work has yielded $o(n)$-time solutions for several basic stringology problems in the setting where the input string(s) is/are given in packed form (the packed setting). These include pattern matching [7] and indexing [31, 41], computing the LZ factorization and BWT [22, 30, 31, 32], the longest common substring [13], the longest palindromic substring [16], the Lyndon array [4], and covers of a string [42]. While for some of the discussed problems, such as pattern matching, optimal $𝒪(n/{\log }_{\sigma }n)$-time algorithms exist, for several others, such as BWT construction, the best known algorithms run in time $𝒪(n\sqrt{\log n}/{\log }_{\sigma }n)$. A recent work of Kempa and Kociumaka [33] shed light on the source of difficulty of several stringology problems for which the state-of-the-art solutions take $𝒪(n\sqrt{\log n}/{\log }_{\sigma }n)$ time.

We are the first to study the problem of counting squares in the packed setting. The problem is formally defined as follows.

Packed Counting Of Distinct Squares
Input: A string $T$ of length $n$ over alphabet $[0..\sigma )$ given in a packed representation. Output: $|\text{squares}(T)|$, where $\text{squares}(T)$ denotes the set of all squares that are equal to some substring of $T$.

We settle the time complexity of the Packed Counting Of Distinct Squares problem, classifiying it as one of the elementary stringology problems that admit an $𝒪(n/{\log }_{\sigma }n)$-time solution in the packed setting.

Moreover, our algorithm can report $k$ distinct squares, for any $k$ between 0 and the actual number of distinct squares in the string, in $𝒪(n/{\log }_{\sigma }n+k)$ time. Our algorithm generalizes readily to powers with higher exponent: for any integer $t\ge 2$, a string of length $n$ contains at most $n/(t-1)$ powers with exponent $t$ [39] and we can compute the actual number of those in a packed string in $𝒪(n/{\log }_{\sigma }n)$ time.

For a string $S$, its positions are numbered as $S[0],\mathrm{\dots },S[|S|-1]$. If $|S|=0$, $S$ is called the empty string. A string consisting of characters $S[i],S[i+1],\mathrm{\dots },S[j]$ is a substring of $S$. A fragment of $S$ is a positioned substring; that is, a fragment $S[i..j]$ represents the substring $S[i],S[i+1],\mathrm{\dots },S[j]$. Where possible, we treat fragments and substrings as equivalent. For two fragments $F=S[a..b]$ and $F^{\prime }=S[a^{\prime }..b^{\prime }]$, we write $F\subseteq F^{\prime }$ if $[a..b]\subseteq [a^{\prime }..b^{\prime }]$. Two fragments $S[a..b]$ and $S[a^{\prime }..b^{\prime }]$ are called neighboring if $[a-1..b+1]\cap [a^{\prime }..b^{\prime }]\ne \mathrm{\varnothing }$. For two neighboring fragments $F=S[a..b]$ and $F^{\prime }=S[a^{\prime }..b^{\prime }]$, by $F\cup F^{\prime }$ we denote the fragment $S[\min (a,a^{\prime })..\max (b,b^{\prime })]$ and by $F\cap F^{\prime }$ we denote the fragment $S[\max (a,a^{\prime })..\min (b,b^{\prime })]$.

We say that a positive integer $p$ is a period of string $S$ if $p\le |S|$ and $S[i]=S[i+p]$ for all $i\in [0..|S|-p)$; equivalently, $S[0..|S|-p)=S[p..|S|)$. Fine and Wilf’s periodicity lemma [25] asserts that if a string of length $n$ has periods $p$ and $q$ such that $p+q\le n$, then the string has period $\gcd (p,q)$. By $\text{per}(S)$ we denote the smallest period of $S$ to which we refer as the period of $S$.

A non-empty string $S$ is called primitive if the equality $S=U^t$ for a positive integer $t$ implies that $t=1$. By ${\text{rot}}_c(S)$ we denote a cyclic rotation of the string $S$, obtained by moving the $c$ first characters of $S$ to its end. A string is called a Lyndon string if it is primitive and lexicographically minimal in the class of its cyclic rotations.

We say that a string $S$ is periodic if $\text{per}(S)\le \frac{1}{2}|S|$ and highly periodic if $\text{per}(S)\le \frac{1}{4}|S|$. The Lyndon root of a periodic string $S$, denoted by $\text{Lroot}(S)$, is the lexicographically smallest rotation of $S[0..\text{per}(S))$. For example, $\text{Lroot}({(\mathrm{𝚊𝚋𝚊𝚊𝚊})}^3\mathrm{𝚊𝚋𝚊})=\mathrm{𝚊𝚊𝚊𝚊𝚋}$.

A run in a string $T$ is a fragment $F=T[a..b]$ that is periodic, that is, $p:=\text{per}(F)\le \frac{1}{2}|F|$, and inclusion-maximal, that is,

• $\mathrm{■}$

  $a=0$ or $T[a-1]\ne T[a-1+p]$ and

• $\mathrm{■}$

  $b=|T|-1$ or $T[b+1]\ne T[b+1-p]$.

We denote the set of runs in $T$ by $\mathrm{𝖱𝗎𝗇𝗌}(T)$. A string of length $n$ contains at most $n$ runs and they can be computed in $𝒪(n)$ time [5], even if the string is over an arbitrary ordered alphabet [23].

The Lyndon position of a run $R=T[a..b]$ with Lyndon root $\lambda$ is the unique position $i\in [a..a+\text{per}(R))$ such that $T[i..i+\text{per}(R))=\lambda$.

A square is a string of the form $X^2=XX$ for a non-empty string $X$. A square $X^2$ is called primitively rooted if $X$ is primitive and non-primitively-rooted otherwise.

We say that a square $X^2$ is generated by a periodic string $U$ if $X^2$ is contained in $U$ and $\text{per}(X^2)=\text{per}(U)$. By the periodicity lemma, in this case $|X|$ is a multiple of $\text{per}(U)$. We denote by $\mathrm{frag}\text{-}\mathrm{squares}(U)$ the set of squares generated by a periodic string $U$.

For a set $𝒳$ of periodic fragments of $T$ we denote

The following observation states that each square in a string is generated by a run.

Unfortunately, from the point of view of counting, the same square string can be generated by many runs. Dealing with squares whose first half is both primitive and (highly) periodic is the most challenging. The next section is devoted to runs that generate such squares.

The next fact follows by using radix sort (with bucket sort).

In this section we describe the structure of runs that generate special squares.

A special square is a square which is primitively rooted and subperiodic. All other squares are called plain.

For two neighboring runs $F,F^{\prime }$ with equal period $p$ in $T$, we have $|F\cap F^{\prime }|\le p-1$ [36]. Two such runs can induce a collection of runs with subperiod $p$. We formalize this structure in the following definition and provide illustrations in Figures 2 and 3.

In this section we show that a representation of all runs in a string of length $n$ over an alphabet $[0..\sigma )$ can be computed in $𝒪(n/{\log }_{\sigma }n)$ time.

First we show how to compute runs with large periods. Some of these runs are grouped in pyramids.

Amir et al. [1] showed how to compute squares and runs in a dynamic string. Their techniques can be interpreted in the so-called PILLAR model, introduced by Charalampopoulos, Kociumaka, and Wellnitz [15]. Recent optimal data structures for $\mathrm{𝖫𝖢𝖯}$ queries [31] and $\mathrm{𝖨𝖯𝖬}$ queries [35] in the packed setting imply that any problem on strings of total length $n$ that can be solved in $𝒪(f(n))$ time in the PILLAR model, can be solved in $𝒪(n/{\log }_{\sigma }n+f(n))$ time in the packed setting. All in all, we obtain the following fact whose proof closely follows [1, 12]; for completeness, it is provided in the full version.

We do not include max-layers in set $𝒵$ as they can be common to many pyramids.

In this work, in all considered clusters of runs, we have $0\in D$.

A $\tau$-run $R$ is a run of length at least $3\tau -1$ with period at most $\frac{1}{3}\tau$.

The next lemma can be proved using tabulation; a proof can be found in the full version.

Putting everything together, we obtain the following proposition. We may need to trim arithmetic progressions of regular layers to avoid double reporting runs with small periods.

The next observation is crucial in counting distinct square substrings of a string. Let us denote by $\mathrm{𝖱𝗎𝗇𝗌}(T,\lambda )$ and $\text{squares}(T,\lambda )$ the sets of runs and squares in $T$ with Lyndon root $\lambda$.

Crochemore et al. [19] considered all runs in the string in groups consisting of runs with equal Lyndon root. The algorithm for grouping of runs that they used consists of the following three steps:

1. 1.

   Computing a Lyndon position for each run.

2. 2.

   Sorting runs with equal periods in the order of the suffixes starting at Lyndon positions. It is guaranteed that runs from the same group are listed consecutively.

3. 3.

   Partitioning the sorted list of runs obtained for each period into groups by issuing an $\mathrm{𝖫𝖢𝖯}$-query for each pair of subsequent runs in the list.

We use Proposition 25 to compute an $𝒪(n/{\log }_{\sigma }n)$-sized representation of all the runs in $T$. For runs with small periods, we use the aforementioned approach combined with tabulation (for runs that are not $\tau$-runs) and the following fact for $\tau$-runs.

A proof of Lemma 28 is given in the full version.

One issue with adapting the aforementioned approach to grouping runs with large periods is that we do not know how to compute the Lyndon positions of $𝒪(n/{\log }_{\sigma }n)$ runs in $T$ if their period is greater than $c{\log }_{\sigma }n$ for a constant $c$, in $𝒪(n/{\log }_{\sigma }n)$ time.

Using cyclic equivalence queries of Kociumaka et al. [35] that allow to check if two substrings of $T$ are cyclic rotations of each other, we can check if two runs have the same Lyndon root in $𝒪(1)$ time after $𝒪(n/{\log }_{\sigma }n)$-time preprocessing, but this is not sufficient for grouping the runs by Lyndon roots. Moreover, it is unknown whether minimal cyclic rotation queries can be implemented efficiently in the packed model. The fastest known solution, by Kociumaka [34], answers minimal cyclic rotation queries in $𝒪(1)$ time but requires $\mathrm{\Theta }(n)$ preprocessing; improving the preprocessing time to sublinear here seems to be challenging.

Instead, we use a string synchronizing set, as defined by Kempa and Kociumaka [31], to select a unique position within each long-period run (that might not be the Lyndon position) in a consistent way that allows us to group such runs by Lyndon roots.

Crucially, string synchronizing sets for small values of $\tau$ can be constructed in optimal time in the packed setting.

Henceforth, we fix $\tau :=\lfloor \frac{1}{18}{\log }_{\sigma }n\rfloor$ and a $\tau$-synchronizing set $\mathrm{𝐒𝐲𝐧𝐜}$ for $T$ computed in $𝒪(n/{\log }_{\sigma }n)$ time using Theorem 31. We next define sparse-Lyndon positions, noting that their existence is only guaranteed for runs whose periods are long enough, and use them to group runs by Lyndon roots.

The following key lemma shows that Lyndon positions can indeed be replaced by sparse-Lyndon positions for the sake of grouping runs by Lyndon roots.