Jonas Ellert

Pawe L Gawrychowski

Garance Gourdel

Optimal Square Detection Over General Alphabets

Squares (fragments of the form xx, for some string x) are arguably the most natural type of repetition in strings. The basic algorithmic question concerning squares is to check if a given string of length n is squarefree, that is, does not contain a fragment of such form. Main and Lorentz [J. Algorithms 1984] designed an O(n log n) time algorithm for this problem, and proved a matching lower bound assuming the so-called general alphabet, meaning that the algorithm is only allowed to check if two characters are equal. As an open question, they asked if there is a faster algorithm if one restricts the size of the alphabet. Crochemore [Theor. Comput. Sci. 1986] designed a linear-time algorithm for constant-size alphabets, and combined with the more recent results his approach in fact implies such an algorithm for linearly-sortable alphabets. Very recently, Ellert and Fischer [ICALP 2021] significantly relaxed this assumption by designing a linear-time algorithm for general ordered alphabets, that is, assuming a linear order on the characters. However, the open question of Main and Lorentz from 1984 remained unresolved for general (unordered) alphabets. In this paper, we show that testing square-freeness of a length-n string over general alphabet of size σ can be done with O(n log σ) comparisons, and cannot be done with o(n log σ) comparisons. We complement this result with an O(n log σ) time algorithm in the Word RAM model.

Introduction

The notion of repetition is a central concept in combinatorics on words and algorithms on strings. In this context, a word or a string is simply a sequence of characters from some finite alphabet Σ. In the most basic version, a repetition consists of two (or more) consecutive occurrences of the same fragment. Repetitions are interesting not only from a purely theoretical point of view, but are also very relevant in bioinformatics [START_REF] Kolpakov | mreps: efficient and flexible detection of tandem repeats in DNA[END_REF]. A repetition could be a square, defined as two consecutive occurrences of the same fragment, a higher power (for example, a cube), or a run. In this paper, we will be mostly working with squares.

The study of squares in strings goes back to the work of Thue published in 1906 [START_REF] Thue | Über unendliche Zeichenreihen[END_REF], who considered the question of constructing an infinite word with no squares. It is easy to see that any sufficiently long binary word must contain a square, and Thue proved that there exists an infinite ternary word with no squares. His result has been rediscovered multiple times, and in 1979 Bean, Ehrenfeucht and McNulty [START_REF] Bean | Avoidable patterns in strings of symbols[END_REF] started a systematic study of the so-called avoidable repetitions, see for example the survey by Currie [START_REF] Currie | Pattern avoidance: themes and variations[END_REF].

Combinatorics on words. The basic tool in the area of combinatorics on words is the so-called periodicity lemma. A period of a string T [1..n] is an integer d such that T [i] = T [i+d] for every i ∈ [1, n-d], and the periodicity lemma states that if p and q are both such periods and p + q ≤ n + gcd(p, q) then so is gcd(p, q) [START_REF] Fine | Uniqueness theorems for periodic functions[END_REF]. This was generalised in a myriad of ways, for strings [START_REF] Castelli | Fine and Wilf's theorem for three periods and a generalization of Sturmian words[END_REF][START_REF] Justin | On a paper by Castelli, Mignosi, Restivo[END_REF][START_REF] Tijdeman | Fine and Wilf words for any periods[END_REF], partial words (words with don't cares) [START_REF] Berstel | Partial words and a theorem of Fine and Wilf[END_REF][START_REF] Blanchet-Sadri | Graph connectivity, partial words, and a theorem of Fine and Wilf[END_REF][START_REF] Blanchet-Sadri | Partial words and a theorem of Fine and Wilf revisited[END_REF][START_REF] Idiatulina | Periodic partial words and random bipartite graphs[END_REF][START_REF] Kociumaka | A periodicity lemma for partial words[END_REF][START_REF] Shur | Partial words and the interaction property of periods[END_REF][START_REF] Shur | On the periods of partial words[END_REF], Abelian periods [START_REF] Blanchet-Sadri | Abelian periods, partial words, and an extension of a theorem of Fine and Wilf[END_REF][START_REF] Constantinescu | Fine and Wilf's theorem for abelian periods[END_REF], parametrized periods [START_REF] Apostolico | Periodicity and repetitions in parameterized strings[END_REF], order-preserving periods [START_REF] Gourdel | String periods in the orderpreserving model[END_REF][START_REF] Matsuoka | Generalized pattern matching and periodicity under substring consistent equivalence relations[END_REF], approximate periods [START_REF] Amir | Approximate periodicity[END_REF][START_REF] Amir | Approximate periodicity[END_REF][START_REF] Amir | Approximate period detection and correction[END_REF]. Now, a square can be defined as a fragment of length twice its period. The string a n contains Ω(n 2 ) such fragments, thus from the combinatorial point of view it is natural to count only distinct squares. Fraenkel and Simpson [START_REF] Fraenkel | How many squares can a string contain?[END_REF] showed an upper bound of 2n and a lower bound of n -Θ( √ n) for the maximum number of distinct squares in a length-n string. After a sequence of improvements [START_REF] Deza | How many double squares can a string contain?[END_REF][START_REF] Ilie | A note on the number of squares in a word[END_REF][START_REF] Thierry | A proof that a word of length n has less than 1.5n distinct squares[END_REF], the upper bound was very recently improved to n [START_REF] Brlek | On the number of squares in a finite word[END_REF]. The last result was already generalised to higher powers [START_REF] Li | A note on the maximum number of k-powers in a finite word[END_REF]. Another way to avoid the trivial examples such as a n is to count only maximal periodic fragments, that is, fragments with period at most half of their length and that cannot be extended to the left or to the right without breaking the period. Such fragments are usually called runs. Kolpakov and Kucherov [START_REF] Kolpakov | Finding maximal repetitions in a word in linear time[END_REF] showed an upper bound of O(n) on their number, and this started a long line of work on determining the exact constant [START_REF] Crochemore | Maximal repetitions in strings[END_REF][START_REF] Crochemore | The "runs" conjecture[END_REF][START_REF] Giraud | Not so many runs in strings[END_REF][START_REF] Giraud | Asymptotic behavior of the numbers of runs and microruns[END_REF][START_REF] Puglisi | How many runs can a string contain?[END_REF][START_REF] Rytter | The number of runs in a string: Improved analysis of the linear upper bound[END_REF], culminating in the paper of Bannai et al. [START_REF] Bannai | The "runs" theorem[END_REF] showing an upper bound of n, and followed by even better upper bounds for binary strings [START_REF] Fischer | Beyond the runs theorem[END_REF][START_REF] Holub | Prefix frequency of lost positions[END_REF]. This was complemented by a sequence of lower bounds [START_REF] Franek | An asymptotic lower bound for the maximal number of runs in a string[END_REF][START_REF] Matsubara | A series of run-rich strings[END_REF][START_REF] Matsubara | New lower bounds for the maximum number of runs in a string[END_REF][START_REF] Simpson | Modified Padovan words and the maximum number of runs in a word[END_REF].

Algorithms on strings. In this paper, we are interested in the algorithmic aspects of detecting repetitions in strings. The most basic question in this direction is checking if a given length-n string contains at least one square. Testing square-freeness was first considered by Main and Lorentz [START_REF] Main | An O(n log n) algorithm for finding all repetitions in a string[END_REF], who designed an O(n log n) time algorithm based on a divide-and-conquer approach and a linear-time procedure for finding all new squares obtained when concatenating two strings. In fact, their algorithm can be used to find (a compact representation of) all squares in a given string within the same time complexity. They also proved that any algorithm based on comparisons of characters needs Ω(n log n) such operations to test square-freeness in the worst case. Here, comparisons of characters means checking if characters at two positions of the input string are equal. However, to obtain the lower bound they had to consider instances consisting of even up to n distinct characters, that is, over alphabet of size n. This is somewhat unsatisfactory, and motivates the following open question that was explicitly asked by Main and Lorentz [START_REF] Main | An O(n log n) algorithm for finding all repetitions in a string[END_REF]: Question 1.1. Is there a faster algorithm to determine if a string is square-free if we restrict the size of the alphabet?

Another O(n log n) time algorithm for finding all repetitions was given by Crochemore [START_REF] Crochemore | An optimal algorithm for computing the repetitions in a word[END_REF], who also showed that for constant-size alphabets testing square-freeness can be done in O(n) time [START_REF] Crochemore | Transducers and repetitions[END_REF]. In fact, the latter algorithm works in O(n log σ) time for alphabets of size σ with a linear order on the characters. That is, it needs to test if the character at some position is smaller than the character at another position. In the remaining part of the paper, we will refer to this model as general ordered alphabet, while the model in which we can only test equality of characters will be called general (unordered) alphabet. Later, Kosaraju [START_REF] Kosaraju | Computation of squares in a string (preliminary version)[END_REF] showed that in fact, assuming constant-size alphabet, O(n) time is enough to find the shortest square starting at each position of the input string. Apostolico and Preparata [START_REF] Apostolico | Optimal off-line detection of repetitions in a string[END_REF] provide another O(n log n) time algorithm assuming a general ordered alphabet, based more on data structure considerations than combinatorial properties of words. Finally, a number of alternative O(n log n) and O(n log σ) time algorithms (respectively, for general unordered and general ordered alphabets) can be obtained from the work on online [START_REF] Hong | Efficient on-line repetition detection[END_REF][START_REF] Kosolobov | Online square detection[END_REF][START_REF] Kosolobov | Online detection of repetitions with backtracking[END_REF] and parallel [START_REF] Apostolico | An optimal O(log log n)-time parallel algorithm for detecting all squares in a string[END_REF] square detection (interestingly, this cannot be done efficiently in the related streaming model [START_REF] Merkurev | Searching runs in streams[END_REF][START_REF] Merkurev | Computing the maximum exponent in a stream[END_REF]).

Faster algorithms for testing square-freeness of strings over general ordered alphabets were obtained as a byproduct of the more general results on finding all runs. Kolpakov and Kucherov [START_REF] Kolpakov | Finding maximal repetitions in a word in linear time[END_REF] not only proved that any length-n string contains only O(n) runs, but also showed how to find them in the same time assuming linearly-sortable alphabet. Every square is contained in a run, and every run contains at least one square, thus this in particular implies a linear-time algorithm for testing square-freeness over such alphabets. For general ordered alphabets, Kosolobov [START_REF] Kosolobov | Lempel-Ziv Factorization May Be Harder Than Computing All Runs[END_REF] showed that the decision tree complexity of this problem is only O(n), and later complemented this with an efficient O(n(log n) 2/3 ) time algorithm [START_REF] Kosolobov | Computing runs on a general alphabet[END_REF] (still using only O(n) comparisons). The time complexity was then improved to O(n log log n) by providing a general mechanism for answering longest common extension (LCE) queries for general ordered alphabets [START_REF] Gawrychowski | Faster longest common extension queries in strings over general alphabets[END_REF], and next to O(nα(n)) by observing that the LCE queries have additional structure [START_REF] Crochemore | Near-optimal computation of runs over general alphabet via non-crossing LCE queries[END_REF]. Finally, Ellert and Fischer provided an elegant O(n) time algorithm, thus fully resolving the complexity of square detection for general ordered alphabets. However, for general (unordered) alphabets the question of Main and Lorentz remains unresolved, with the best upper bound being O(n log n), and only known to be asymptotically tight for alphabets of size Θ(n).

General alphabets. While in many applications one can without losing generality assume some ordering on the characters of the alphabet, no such ordering is necessary for defining what is a square. Thus, it is natural from the mathematical point of view to seek algorithms that do not require such an ordering to efficiently test squarefreeness. Similar considerations have lead to multiple beautiful results concerning the pattern matching problem, such as constant-space algorithms [START_REF] Breslauer | Efficient String Algorithmics[END_REF][START_REF] Galil | Time-space-optimal string matching[END_REF], or the works on the exact number of required equality comparisons [START_REF] Cole | Tighter upper bounds on the exact complexity of string matching[END_REF][START_REF] Cole | Tighter lower bounds on the exact complexity of string matching[END_REF] More recent examples include the work of Duval, Lecroq, and Lefebvre [START_REF] Duval | Linear computation of unbordered conjugate on unordered alphabet[END_REF] on computing the unbordered conjugate/rotation, and Kosolobov [START_REF] Kosolobov | Finding the leftmost critical factorization on unordered alphabet[END_REF] on finding the leftmost critical point.

Main results. We consider the complexity of checking if a given string T [1.

.n] containing σ distinct characters is square-free. The input string can be only accessed by issuing comparisons T [i] ?

= T [j], and the value of σ is not assumed to be known. We start by analysing the decision tree complexity of the problem. That is, we only consider the required and necessary number of comparisons, without worrying about an efficient implementation. We show that, even if the value of σ is assumed to be known, Ω(n log σ) comparisons are required.

Theorem 1.1. For any integers n and σ with 8 ≤ σ ≤ n, there is no deterministic algorithm that performs at most n ln σ -3.6n = O(n ln σ) comparisons in the worst case, and determines whether a length-n string with at most σ distinct symbols is square-free.

Next, we show that in fact O(n log σ) comparisons are sufficient. We stress that the value of σ is not assumed to be known. In fact, as a warm-up for the above theorem, we first prove that finding a sublinear multiplicative approximation of this value requires nσ 8 comparisons. This does not contradict the claimed upper bound, as we are only saying that the number of comparisons used on a particular input string is at most O(n log σ), but might actually be smaller. Thus, it is not possible to extract any meaningful approximation of the value of σ from the number of used comparisons.

Theorem 1.2. Testing square-freenes of a length-n string that contains σ distinct symbols from a general unordered alphabet can be done with O(n log σ) comparisons.

The proof of the above result is not efficient in the sense that it only restricts the overall number of comparisons, and not the time to actually figure out which comparisons should be used. A direct implementation results in a quadratic time algorithm. We first show how to improve this to O(n log σ + n log * n) (while still keeping the asymptotically optimal O(n log σ) number of comparisons), and finally to O(n log σ). In this part of the paper, we assume the Word RAM model with word of length Ω(log n). We stress that the input string is still assumed to consist of characters that can be only tested for equality, that is, one should think that we are given oracle access to a functions that, given i and j, checks whether

T [i] = T [j].
Theorem 1.3. Testing square-freeness of a length-n string that contains σ distinct symbols from a general unordered alphabet can be implemented in O(n log σ) comparisons and time.

Altogether, our results fully resolve the open question of Main and Lorentz for the case of general unordered alphabets and deterministic algorithms. We leave extending our lowerbound to randomised algorithms as an open questions.

Overview of the methods. As mentioned before, Main and Lorentz [START_REF] Main | An O(n log n) algorithm for finding all repetitions in a string[END_REF] designed an O(n log n) time algorithm for testing square-freeness of length-n strings over general alphabets. The high-level idea of their algorithm goes as follows. They first designed a procedure for checking, given two strings x and y, if their concatenation contains a square that is not fully contained in x nor y in O(|x| + |y|) time. Then, a divide-andconquer approach can be used to detect a square in the whole input string in O(n log n) total time. For general alphabets of unbounded size this cannot be improved, but Crochemore [START_REF] Crochemore | Transducers and repetitions[END_REF] showed that, for general ordered alphabets of size σ, a faster O(n log σ) time algorithm exists. The gist of this approach is to first obtain the so-called f -factorisation of the input string (related to the well-known Lempel-Ziv factorisation), that in a certain sense "discovers" repetitive fragments. Then, this factorisation can be used to apply the procedure of Main and Lorentz on appropriately selected fragments of the input strings in such a way that the leftmost occurrence of every distinct square is detected, and the total length of the strings on which we apply the procedure is only O(n). The factorisation can be found in O(n log σ) time for general ordered alphabets of size σ by, roughly speaking, constructing some kind of suffix structure (suffix array, suffix tree or suffix automaton). For general (unordered) alphabets, computing the f -factorisation (or anything similar) seems problematic, and in fact we show (as a corollary of our lower bound on approximating the alphabet size) that computing the f -factorisation or Lempel-Ziv-factorisation (LZ-factorisation) of a given length-n string containing σ distinct characters requires nσ 24 equality tests. Thus, we need another approach. Additionally, the O(n) time algorithm of Ellert and Fischer [START_REF] Ellert | Linear Time Runs Over General Ordered Alphabets[END_REF] hinges on the notion of Lyndon words, which is simply not defined for strings over general alphabets. Thus, at first glance it might seem that Θ(nσ) is the right time complexity for testing square-freeness over length-n strings over general alphabets of size σ. At the same time, due to the Ω(n log n) lower bound of Main and Lorentz for testing square-freeness of length-n string consisting of up to n distinct characters, one might hope for an O(n log σ) time algorithm when there are only σ distinct characters.

We begin our paper with a lower bound of Θ(n log σ) for such strings. Intuitively, we show that testing square-freeness has the direct sum property: n σ instances over length-σ strings can be combined into a single instance over length-n string. As in the proof of Main and Lorentz, we use the adversarial method. While the underlying calculation is essentially the same, we need to appropriately combine the smaller instances, which is done using the infinite square-free Prouhet-Thue-Morse sequence, and use significantly more complex rules for resolving the subsequent equality tests. As a warm-up for the adversarial method, we prove that computing any meaningful approximation of the number of distinct characters requires Ω(nσ) such tests, and that this implies the same lower bound on computing the f -factorisation and the Lempel-Ziv factorisation.

We then move to designing an approach that uses O(n log σ) equality comparisons to test square-freeness. First, we introduce the notion of ∆-approximate LZ factorisation. Intuitively, its goal is to "capture" all sufficiently long squares, while the original LZ factorisation (or f -factorisation) captures all squares. Each phrase in a ∆approximate LZ factorisation consists of a head of length at most ∆ and a tail (possibly empty) that must occur at least once before, such that the whole phrase is at least as long as the classical LZ phrase starting at the same position. Contrary to the classical LZ factorisation, this factorisation is not unique. The advantage of our modification is that there are fewer phrases (and there is more flexibility as to what they should be), and hence one can hope to compute such factorisation more efficiently. Indeed, we provide such an efficient construction method using the so-called ∆-difference covers and sparse suffix trees. This method is then applied in log log n phases, corresponding to smaller and smaller estimates on the size of the alphabet. Constructing the sparse suffix tree and then finding a ∆-approximate LZ factorisation uses sufficiently few equality tests, unless we notice that there are many distinct characters in the alphabet. In such case, by carefully adjusting the parameters, we can afford switching to the approach of Main and Lorentz on sufficiently short fragments of the input string. After computing a ∆-approximate LZ factorisation, we apply the procedure of Main and Lorentz on fragments around a sufficiently long tail of some phrase. The overall number of equality tests used in all such invocations is amortised over all phases. More precisely, during a given phase, we avoid looking for squares in a fragment fully contained in a tail from an earlier phase.

The above approach uses an asymptotically optimal number of equality tests in the worst case, but does not result in an efficient algorithm. The main bottleneck is constructing the sparse suffix trees. However, it is not hard to provide an efficient implementation using the general mechanism for answering LCE queries for strings over general alphabets [START_REF] Gawrychowski | Faster longest common extension queries in strings over general alphabets[END_REF]. Unfortunately, the best known approach for answering such queries incurs an additional O(n log * n) in the time complexity, even if the size of the alphabet is constant. We overcome this technical hurdle by applying the recent notion of string synchronizing sets introduced by Kempa and Kociumaka [START_REF] Kempa | String synchronizing sets: sublinear-time BWT construction and optimal LCE data structure[END_REF]. We note that constructing such sets efficiently requires assuming linearly-sortable alphabets, therefore we can only apply this mechanism on sufficiently short fragments of the input strings, which leads to some additional technical difficulties.

It is relatively straightforward to extend our intermediate O(n log * n) time algorithm to reporting all runs in the same time complexity. Adapting the final O(n) time algorithm to this end is left as an open question.

Preliminaries

Strings. A string of length n is a sequence T [START_REF] Allouche | The ubiquitous Prouhet-Thue-Morse Sequence[END_REF] . . . T [n] of characters from a finite alphabet Σ of size σ. The substring T [i..j] is the string

T [i] • • • T [j]
, whereas the fragment T [i..j] refers to the specific occurrence of T [i..j] starting at position i in T . If i > j, then T [i..j] is the empty string. T [i..j) is a shortcut for T [i..j -1]. Similarly, we write [i, j] = [i, j + 1) as a shortcut for the integer interval {i, . . . , j}. Given two positions i ≤ j, their longest common extension (LCE) is the length of the longest common prefix between suffixes T [i..n] and T [j..n], formally defined as lce(i,

j) = lce(j, i) = max{ℓ | ℓ ∈ {0, . . . , n -j + 1} ∧ T [i..i + ℓ) = T [j..j + ℓ)}. Definition 2.1. A positive integer p is a period of a string T [1..n] if T [i] = T [i + p] for every i ∈ {1, . . . n -p}.
The smallest such p is called the period of T [1..n], and we call a string periodic if its period p is at most n 2 . Computational model. For a general unordered alphabet Σ, the only allowed operation on the characters is comparing for equality. In particular, there is no linear order on the alphabet. Unless explicitly stated otherwise, we will only use such comparisons. A general ordered alphabet has a total order, such that comparisons of the type less-equals are possible.

In the algorithmic part of the paper, we assume the standard unit-cost Word RAM model with words of length Ω(log n), but the algorithm is only allowed to access the input string T [1..n] by comparisons

T [i] ? = T [j].
We say that a string of length n is over a linearly-sortable alphabet, if we can sort the n symbols of the string in O(n) time. Note that whether or not an alphabet is linearly-sortable depends not only on the alphabet, but also on the string. For example, the alphabet Σ = {1, . . . , m O(1) } is linearly-sortable for strings of length n = Ω(m) (e.g., using radix sort), but it is unknown whether it is linearly-sortable for all strings of length n = o(m) [START_REF] Han | Integer sorting in O(n √ log log n) expected time and linear space[END_REF]. Our algorithm will internally use strings over linearly-sortable alphabets. We stress that in such strings the characters are not the characters from the input string, but simply integers calculated by the algorithm. Note that every linearly-sortable alphabet is also a general ordered alphabet.

Squares. A square is a length-2ℓ fragment of period ℓ. The following theorem is a classical result by Main and Lorentz [START_REF] Main | An O(n log n) algorithm for finding all repetitions in a string[END_REF]. The proof of the above theorem is based on running a divide-and-conquer procedure using the following lemma.

Lemma 2.1. Given two strings x and y over a general alphabet, we can test if there is a square in xy that is not fully contained in x nor y in O(|x| + |y|) time and comparisons.

Assuming a general ordered alphabet, it is possible to test square-freenes in linear time. This follows from the approach by Ellert and Fischer [START_REF] Ellert | Linear Time Runs Over General Ordered Alphabets[END_REF], who showed that all runs (maximal repetitions) of a string over a general ordered alphabet can be computed in O(n) time. As mentioned earlier, each run contains a square, and each square is contained in a run. Thus, the string contains a square if and only if it contains a run.

of T [1..n] consists of z phrases f 1 , . . . , f z such that the concatenation f 1 . . . f z is equal to T [1..n] and each f i is the unique LZ phrase starting at position 1 + i-1 j=1 |f j |.
Tries. Given a collection S = {T 1 , . . . , T k } of strings over some alphabet Σ, its trie is a rooted tree with edge labels from Σ. For any node v, the concatenation of the edge labels from the root to the node spells a string. The string-depth of a node is the length of the string that it spells. No two nodes spell the same string, i.e., for any node, the labels of the edges to its children are pairwise distinct. Each leaf spells one of the T i , and each T i is spelled by either an internal node or a leaf.

The compacted trie of S can be obtained from its (non-compacted) trie by contracting each path between a leaf or a branching node and its closest branching ancestor into a single edge (i.e., by contraction we eliminate all non-branching internal nodes). The label of the new edge is the concatenation of the edge labels of the contracted path in root to leaf direction. Since there are at most k leaves and all internal nodes are branching, there are O(k) nodes in the compacted trie. Each edge label is some substring T i [s..e] of the string collection, and we can avoid explicitly storing the label by instead storing the reference ⟨i, s, e⟩. Thus O(k) words are sufficient for storing the compacted trie. Consider a string T ′ that is spelled by a node of the non-compacted trie. We say that T ′ is explicit, if and only if it is spelled by a node of the compacted trie. Otherwise T ′ is implicit.

The suffix tree of a string T [1.

.n] is the compacted trie containing exactly its suffixes {T [i.

.n] | i ∈ {1, . . . , n}}. It is one of the most fundamental data structures in string algorithmics, and is widely used, e.g., for compression and indexing [START_REF] Gusfield | Algorithms on Strings, Trees, and Sequences -Computer Science and Computational Biology[END_REF]. The suffix tree can be stored in O(n) words of memory, and for linearly-sortable alphabets it can be computed in O(n) time [START_REF] Farach | Optimal suffix tree construction with large alphabets[END_REF]. The sparse suffix tree of T for some set B ⊆ {1, . . . , n} of sample positions is the compacted trie containing exactly the suffixes {T

[i..n] | i ∈ B}. It can be stored in O(|B|) words of memory.
We assume that T is terminated by some special symbol T [n] = $ that occurs nowhere else in T . This ensures that each suffix is spelled by a leaf, and we label the leaves with the respective starting positions of the suffixes. Note that for any two leaves i ̸ = j, their lowest common ancestor (i.e., the deepest node that is an ancestor of both i and j) spells a string of length lce(i, j).

Lower Bounds

In this section, we show lower bounds on the number of symbol comparisons required to compute a meaningful approximation of the alphabet size (Section 3.1) and to test square-freeness (Section 3.2). For both bounds we use an adversarial method, which we briefly outline now.

The present model of computation may be interpreted as follows. An algorithm working on a string over a general unordered alphabet has no access to the actual string. Instead, it can only ask an oracle whether or not there are identical symbols at two positions. The number of questions asked is exactly the number of performed comparisons. In order to show a lower bound on the number of comparisons required to solve some problem, we describe an adversary that takes over the role of the oracle, forcing the algorithm to perform as many symbol comparisons as possible.

We use a conflict graph G = (V, E) with V = {1, . . . , n} and E ⊆ V 2 to keep track of the answers given by the adversary. The nodes directly correspond to the positions of the string. Initially, it holds E = ∅ and all nodes are colorless, which formally means that they have color γ(i) = ⊥. During the algorithm execution, the adversary may assign colors from the set Σ = {0, . . . , n -1} to the nodes, which can be seen as permanently fixing the alphabet symbol at the corresponding position (i.e., each node gets colored at most once). The rule used for coloring nodes depends on the lower bound that we want to show (we describe this in detail in the respective sections). Apart from this coloring rule, the general behaviour of the adversary is as follows. Whenever the algorithm asks whether T [i] = T [j] holds, the adversary answers "yes" if and only if γ(i) = γ(j) ̸ = ⊥. Otherwise, it answers "no" and inserts an edge (i, j) into E. Whenever the adversary assigns the color of a node, it has to choose a color that is not used by any of the adjacent nodes in the conflict graph. This ensures that the coloring does not contradict the answers given in the past.

Let us define a set T ⊆ Σ n of strings that is consistent with the answers given by the adversary. A string

T ∈ Σ n is a member of T if ∀i ∈ V : γ(i) ∈ {⊥, T [i]} ∧ ∀i, j ∈ V : (T [i] = T [j]) =⇒ (i, j) / ∈ E.
Note that T changes over time. Initially (before the algorithm starts), it holds T = Σ n . With every question asked, the algorithm might eliminate some strings from T . However, there is always at least on string in T , which can be obtained by coloring each colorless node in a previously entirely unused color.

Approximating the Alphabet Size

Given a string T [1.
.n] of unknown alphabet size σ ≥ 2, assume that we want to compute an approximation of σ. We show that if an algorithm takes at most nσ 8 comparisons in the worst-case, then it cannot distinguish strings with at most σ distinct symbols from strings with at least n 2 distinct symbols. Thus, any meaningful approximation of σ requires Ω(nσ) comparisons.

For the sake of the proof, consider an algorithm that performs at most nσ 8 comparisons when given a length-n string with at most σ ≥ 2 distinct symbols. We use an adversary as described at the beginning of Section 3, and ensure that the set T of strings consistent with the adversary's anwers always contains a string with at most σ distinct symbols. Thus, the algorithm terminates after at most nσ 8 comparisons. At the same time, we ensure that T also contains a string with at least n 2 distinct symbols, which yields the desired result. The adversary is equipped with the following coloring rule. All colors are from {1, . . . , σ}. Whenever the degree of a node in the conflict graph becomes σ -1, we assign its color. We avoid the colors of the σ -1 adjacent nodes in the conflict graph. At any moment in time, we could hypothetically complete the coloring by assigning one of the colors {1, . . . , σ} to each colorless node, avoiding the colors of adjacent nodes. This way, each node gets assigned one of the σ colors, which means that T contains a string with at most σ distinct symbols. It follows that the algorithm terminates after at most nσ 8 comparisons. Each comparison may increase the degree of two nodes by one. Thus, after nσ 8 comparisons, there are at most nσ 8 • 2 σ-1 ≤ n 2 nodes with degree at least σ -1. Therefore, at least n 2 nodes are colorless. We could hypothetically color them in n 2 distinct colors, which means that T contains a string with at least n 2 distinct symbols. This leads to the following result.

Theorem 3.1. For any integers n and σ with 2 ≤ σ < n 2 , there is no deterministic algorithm that performs at most nσ 8 equality-comparisons in the worst case, and is able to distinguish length-n strings with at most σ distinct symbols from length-n strings with at least n 2 distinct symbols.

The theorem implies lower bounds on the number of comparisons needed to compute the LZ factorisation (as defined in Section 2) and the f -factorisation. In the unique f -factorisation T = f 1 f 2 . . . f z , each factor f i is either a single symbol that does not occur in f 1 . . . f i-1 , or it is the fragment of maximal length such that f i occurs twice in f 1 . . . f i . The blocks are of length σ 4 = 4. The gray nodes are exactly the starting positions of the blocks and contain the symbols of the ternary Thue-Morse sequence v = 2, 1, 0, 2, 0, 1, 2, . . . , which is square-free. We assume that the colored nodes were colored in the following order: 2, 6, 8, 7, 15, 16, 14. At the time of coloring node 8, we had to avoid colors 0, 1, 2 (because they are reserved for the separator positions), 3 (because the adjacent node 2 already has color 2), and 4 (because node 6 is in the same block and already has color 4). The algorithm has not eliminated all squares yet. For example, nodes 10 and 11 with [START_REF] Bender | The LCA problem revisited[END_REF][START_REF] Berstel | Partial words and a theorem of Fine and Wilf[END_REF] / ∈ E are adjacent to nodes of colors {3, 6, 5} ∪ {5, 3, 4}. Thus, any of the colors {0, 1, 2} ∪ {7, . . . , 15} can be assigned to both nodes, enforcing the square T [10. .11]. As visualized on the right, an edge of length ℓ eliminates at most ℓ squares.

Corollary 3.1. For any integers n and σ with 2 ≤ σ < n 4 , there is no deterministic algorithm that performs at most (n-1)σ 16 equality-comparisons in the worst case, and computes the f -factorisation of a length-n string with at most σ distinct symbols.

Proof. For some string

T = T [1]T [2] . . . T [ n 2 ] with σ distinct symbols, let T ′ = T [1]T [1]T [2]T [2] . . . T [ n 2 ]T [ n 2
] be the length-n string with σ distinct symbols constructed by doubling each character of T . The alphabet size of T is exactly the number of length-one phrases in the f -factorisation of T ′ starting at odd positions in T ′ . Thus, by Theorem 3.1, we need nσ 16 = |T |σ 8 comparisons to find the f -factorisation of T ′ . We assumed that n is even, and account for odd n by adjusting the bound to (n-1)σ 16 .

Corollary 3.2. For any integers n and σ with 3 ≤ σ < n 6 + 1, there is no deterministic algorithm that performs at most (n-2)(σ-1) 24 equality-comparisons in the worst case, and computes the Lempel-Ziv factorisation of a length-n string with at most σ distinct symbols.

Proof. For some string T = T [1]T [START_REF] Amir | Approximate periodicity[END_REF] . . . T [ n 3 ] with σ -1 distinct symbols, let T ′ be the length-n string with σ distinct symbols constructed by doubling every character of T with a separator in between, i.e.,

T ′ = T [1]T [1]#T [2]T [2]# . . . #T [ n 3 ]T [ n 3 ]#.
The first occurrence of character x in T corresponds to the first occurrence of xx# in T ′ , thus the preceding phrase (possibly of length one) ends at the first x in the first occurrence of xx#, and the subsequent phrase must be x#. Then, for the later occurrences of xx# we cannot have that x# is a phrase. Consequently, the alphabet size of T is exactly the number of length-two phrases in the Lempel-Ziv factorisation of T ′ starting at positions i ≡ 2 (mod 3) in T ′ . Thus, by Theorem 3.1, we need n(σ-1) 24

= |T |(σ-1)

8

comparisons to find the LZ factorisation of T ′ . We assumed that n is divisible by 3, and account for this by adjusting the bound to (n-2)(σ-1) 24 .

3.2 Testing Square-Freeness In this section, we prove that testing square-freeness requires at least n ln σ-3n comparisons (even if σ is known). The proof combines the idea behind the original Ω(n lg n) lower bound by Main and Lorentz [START_REF] Main | An O(n log n) algorithm for finding all repetitions in a string[END_REF] with the adversary described at the beginning of Section 3. This time, we ensure that T always contains a square-free string with at most σ distinct symbols. At the same time, we try to ensure that T also contains a string with at least one square. We will show that we can maintain this state until at least n ln σ -3n comparisons have been performed.

The string (or rather family of strings) constructed by the adversary is organized in 4n σ non-overlapping blocks of length σ 4 (we assume σ 4 ∈ N and 8 ≤ σ ≤ n). Each block begins with a special separator symbol. More precisely, the first symbol of the k-th block is the k-th symbol of a ternary square-free word over the alphabet {0, 1, 2} (e.g., the distance between the k th and (k + 1) th occurrence of 0 in the Prouhet-Thue-Morse sequence, also known as the ternary Thue-Morse-Sequence, see [START_REF] Allouche | The ubiquitous Prouhet-Thue-Morse Sequence[END_REF]Corollary 1]). Initially, the adversary colors the nodes that correspond to the separator positions in their respective colors from {0, 1, 2}. All remaining nodes will later get colors other than {0, 1, 2}. Any fragment crossing a block boundary can be projected on the colors {0, 1, 2}, and by construction the string cannot contain a square. Thus, the separator symbols ensure that there is no square crossed by a block boundary, which implies that the string is square-free if and only if each of its blocks is square-free.

During the algorithm execution, we use the following coloring rule. The available colors are {3, . . . , σ -1}. Whenever the degree of a node becomes σ 4 , we assign its color. We avoid not only the at most σ 4 colors of already colored neighbors in the conflict graph, but also the less than σ 4 colors of nodes within the same block (due to σ ≥ 8, there are at least σ -3 -σ 2 ≥ 1 colors available). An example of the conflict graph is provided in Fig. 1. At any moment in time, we could hypothetically complete the coloring by assigning one of the colors {3, . . . , σ -1} to each colorless node, avoiding colors of adjacent nodes and colors of nodes in the same block. Afterwards, each node holds one of the σ colors, but no two nodes within the same block have the same color. Thus, each block is square-free, and therefore T always contains a square-free string with at most σ distinct symbols. Now we consider the state of the conflict graph after the algorithm has terminated. We are particularly concerned with consecutive ranges of colorless nodes. The following lemma states that for each such range, the algorithm either performed many comparisons, or we can enforce a square within the range.

Lemma 3.1. Let R = {i, . . . , j} ⊂ V be a consecutive range of m = j -i + 1 colorless nodes in the conflict graph. Then either E ∩ R 2 ≥ ⌊m/2⌋ ℓ=1 m-2ℓ+1 ℓ
, or there is a string T ∈ T with at most σ distinct symbols such that T [i..j] contains a square.

Proof. We say that an integer interval [x, x + 2ℓ -1] with i ≤ x < (x + 2ℓ -1) ≤ j has been eliminated, if for some y with x ≤ y < x + ℓ there is an edge (y, y + ℓ) in the conflict graph. If such an edge exists, then (by the definition of T ) all strings T ∈ T satisfy T [y] ̸ = T [y + ℓ]. Thus T [x..x + 2ℓ -1] is not a square for any of them. Now we show that if [x, x + 2ℓ -1] has not been eliminated, then there exists a string T ∈ T such that T [x..x + 2ℓ -1] is a square. For this purpose, consider any position y with x ≤ y < x + ℓ, i.e., a position in the first half of the potential square. Since [x, x + 2ℓ -1] has not been eliminated, (y, y + ℓ) is not an edge in the conflict graph. It follows that we could assign the same color to y and y + ℓ. We only have to avoid the at most 2 • ( σ 4 -1) colors of adjacent nodes of both y and y + ℓ in the conflict graph. Thus there are σ 2 + 2 appropriate colors that can be assigned to both nodes. Unlike during the algorithm execution, we do not need to avoid the special separator colors or the colors in the same block; since we are trying to enforce a square, we do not have to worry about accidentally creating one. By applying this coloring scheme for all possible choices of y, we enforce that all strings T ∈ T have a square T [x..x + 2ℓ -1]. Note that by coloring additional nodes after the algorithm terminated, we only remove elements from T . Thus, the strings with square T [x..x + 2ℓ -1] were already in T when the algorithm terminated. It follows that, if the algorithm actually guarantees square-freeness, then it must have eliminated all possible intervals [x, x + 2ℓ -1] with i ≤ x < (x + 2ℓ -1) ≤ j.

While each interval needs at least one edge to be eliminated, a single edge eliminates multiple intervals. However, all the intervals eliminated by an edge must be of the same length. Now we give a lower bound on the number of edges needed to eliminate all intervals of length 2ℓ. Any edge (y, y + ℓ) eliminates ℓ intervals, namely the intervals [x, x + 2ℓ -1] that satisfy x ≤ y < x + ℓ. Within R, we have to eliminate m -2ℓ + 1 intervals of length 2ℓ, namely the intervals [x, x + 2ℓ -1] that satisfy i ≤ x ≤ j -2ℓ + 1 (see right side of Fig. 1). Thus we need at least m-2ℓ+1 ℓ edges to eliminate all squares of length 2ℓ. Finally, by summing over all possible values of ℓ, we need at least

⌊m/2⌋ ℓ=1 m-2ℓ+1 ℓ
edges to eliminate all intervals in R. Note that the edges used for elimination have both endpoints in R, and are thus contained in

E ∩ R 2 . Consequently, if E ∩ R 2 < ⌊m/2⌋ ℓ=1 m-2ℓ+1 ℓ
, then not all intervals have been eliminated, and there is a string in T that contains a square.

Finally, we show that the algorithm either performed at least Ω(n lg σ) comparisons, or there is a string T ∈ T that contains a square. Let c 1 , c 2 , . . . , c k be exactly the colored nodes. Initially (before the algorithm execution), the adversary colored 4n σ nodes. Thus k ≥ 4n σ , and there are k -4n σ nodes that have been colored after their degree reached σ 4 . Therefore, the sum of degrees of all colored nodes is at least (k edges, where m i = c i+1 -c i -1. (No edge gets counted more than once because the ranges are non-overlapping, and both endpoints of the respective edges are within the range.) Thus, in order to verify square-freeness, the algorithm must have performed at least k i=1 e i + σk-5n 8 comparisons. The remainder of the proof consists of simple algebra. First, we provide a convenient lower bound for e i (explained below):

-4n σ ) • σ 4 ≥ σk-4n-σ 4 ≥ σk-5n
e i = ⌊mi/2⌋ ℓ=1 m i -2ℓ + 1 ℓ = ⌈mi/2⌉ ℓ=1 m i -2ℓ + 1 ℓ ≥ (m i + 1)     ⌈mi/2⌉ ℓ=1 1 ℓ   -1   > (m i + 1) • (ln m i 2 - 1 2 ) = (m i + 1) • ln m i 2 √ e ≥ (m i + 1) • ln m i + 1 2.5 √ e
We can replace ⌊m i /2⌋ with ⌈m i /2⌉ because if m i is odd the additional summand equals zero. The first inequality uses simple arithmetic operations. The second inequality uses the classical lower bound (ln x + 1 2 ) < H x of harmonic numbers. The last inequality holds for m i ≥ 4. For m i < 4 the result becomes negative and is thus still a correct lower bound for the number of comparisons. We obtain:

k i=1 (m i + 1) • ln m i + 1 2.5 √ e
comparisons within colorless ranges

+ σk -5n 8 comparisons for colored nodes ≥ n • ln n 2.5 √ ek + σk -5n 8 = n • ln σ 2.5 √ ex + xn -5n 8 = n • ln σ + n • x -5 8 -ln 2.5 √ ex > n • ln σ -3.12074n
The first step follows from k i=1 (m i + 1) = n and the log sum inequality (see [START_REF] Cover | Elements of information theory[END_REF]Theorem 2.7.1]). In the second step we replace k by using x = σk n . The third step uses simple arithmetic operations. The last step is reached by substituting x = 8, which minimizes the equation. Finally, we assumed that σ is divisible by 4. We account for this by adjusting the lower bound to n ln(σ -3) -3.12074n, which is larger than n ln σ -3.6n for σ ≥ 8.

Theorem 1.1. For any integers n and σ with 8 ≤ σ ≤ n, there is no deterministic algorithm that performs at most n ln σ -3.6n = O(n ln σ) comparisons in the worst case, and determines whether a length-n string with at most σ distinct symbols is square-free.

Upper Bound

In this section, we consider the problem of testing square-freeness of a given string. We introduce an algorithm that decides whether or not a string is square-free using only O(n lg σ) comparisons, matching the lower bound from Section 3.2. Note that this algorithm is not yet time efficient because, apart from the performed symbol comparisons, it uses other operations that are expensive in the Word RAM model. A time efficient implementation of the algorithm will be presented in Section 5, where we first achieve O(n lg σ + n log * n) time, and then improve this to O(n lg σ) time.

High-Level Overview of the Upper Bound Algorithm As discussed earlier, one way of detecting squares uses the f -factorisation of the string, which is similar to its LZ factorisation. However, as shown in Corollaries 3.1 and 3.2, we cannot compute either of these factorisations over a general unordered alphabet in o(nσ) comparisons. Therefore, we will instead use a novel type of factorisation that can be seen as an approximate version of the LZ factorisation. The high-level structure of our algorithm (and of the remainder of this section) is as follows:

• Before introducing the factorisation, we show how to compute a sparse suffix tree while trying to use as few symbol comparisons as possible. The sample positions will later be taken from a so-called difference cover with convenient synchronizing properties.

• The approximate factorisation is parametrized with some positive integer ∆. For larger ∆, we need fewer comparisons to compute the factorisation. However, with larger ∆ we also loose the ability to find short squares. We show how to compute the factorisation from a sparse suffix tree, where the number of samples is inverse proportional to ∆.

• We show how to detect squares of length ≥ 8∆ from the ∆-approximate factorisation.

• A first simple algorithm fixes ∆ depending on n and σ (assuming that σ is known), and uses the approximate LZ factorisation to find all squares of length at least 8∆. It then finds all the shorter squares by dividing the string in blocks of length 8∆, and applying the original algorithm by Main & Lorentz (Theorem 2.1) on each block pair. Our choice of ∆ leads to O(n(lg σ + lg lg n)) comparisons.

• A more sophisticated algorithm starts with a large ∆ = Ω(n), and then progressively decreases ∆ in at most O(lg lg n) phases, where later phases detect shorter squares. Since we cannot afford Ω(n) comparisons per phase, we use a deactivation technique, where whenever we perform a large number of comparisons in a phase, we will discard a large part of the string in all following phases. This leads to optimal O(n lg σ) comparisons. = T [y], we check if x and y are in the same component of the union-find structure, and if so immediately return that T [x] = T [y] without performing any comparisons. Otherwise, we issue the query and if it returns that T [x] = T [y] we merge the components of x and y. Thus, the total number of issued queries with positive answer, over all invocations of the lemma, is less than n, and it remains to bound the number of issued queries with negative answer.

Sparse Suffix Trees and Difference Covers

Considering inserting the suffixes T [i j .

.n] one-by-one into an initially empty sparse suffix tree T . To insert the next suffix, we descend from the root of T to identify the node u corresponding to the longest common prefix of T [i j ..n] and the already inserted suffixes, make u explicit unless it is explicit already, and then add an edge from u to a new leaf corresponding to the whole T [i j ..n]. We say that the insertion procedure terminates at u. u can be identified with only O(σ log b) comparisons with negative answers as follows. Let the current node (initially, the root of T ) be v, and its children v 1 , . . . , v d , where d ≤ σ. Here, v can be either explicit or implicit, in the latter case d = 1. We arrange the children of v so that the number of leaves in the subtree rooted at v 1 is at least as large as the number of leaves in the subtree rooted at any other child of v. Then, we compare the character on the edge leading to v 1 with the corresponding character of the current suffix. If they are equal we continue with v 1 , otherwise we compare the characters on the edges leading to v 2 , . . . , v d with the corresponding character of the current suffix one-by-one. Then, we either continue with some v j , j ≥ 2, or terminate at v. To bound the number of comparisons with negative answer, observe that such comparisons only occur when we either terminate at v or continue with v j , j ≥ 2. Whenever we continue with v j , j ≥ 2, the number of leaves in the current subtree rooted at v j decreases at least by a factor of 2 compared to subtree rooted at v (as the subtree rooted at v 1 had the largest number of leaves). Thus, during the whole descent from the root performed during an insertion this can happen only at most 1 + log b times. Every time we do not continue in the subtree v 1 we might have up to d ≤ σ comparisons with negative answer, thus the total number of such comparisons is as claimed1 . Now we describe the sample positions that we will later use to compute the approximate LZ factorisation. A set S ⊆ N is called a t-cover of {1, . . . , n} if there is a constant-time computable function h such that, for any 1 ≤ i, j ≤ n -t + 1, we have 0 ≤ h(i, j) < t and i + h(i, j), j + h(i, j) ∈ S. Lemma 4.2. For any n and t ≤ n, there exists a t-cover D(t) of {1, . . . , n} with size O(n/ √ t). Furthermore, its elements can be enumerated in time proportional to their number. Proof. We use the well-known combinatorial construction known as difference covers, see e.g. [START_REF] Maekawa | A √ N algorithm for mutual exclusion in decentralized systems[END_REF]. Let r = ⌊ √ t⌋ and define D(t) = {i ∈ {1, . . . , n} : i mod r = 0 or i mod r 2 ∈ {0, . . . , r -1}}. By definition, |D(t)| ≤ ⌊n/r⌋ + ⌊n/r 2 ⌋r = O(n/r) = O(n/ √ t). The function h(i, j) is defined as a + b • r, where a = (r -i) mod r and b = (r -⌊(j + a)/r⌋) mod r. Note that i + h(i, j) ≤ n and j + h(i, j) ≤ n. Then, i + (a + b • r) = 0 (mod r), while ⌊(j + (a + b • r))/r⌋ = ⌊(j + a)/r + b⌋ = 0 mod r implies j + h(i, j) mod r 2 ∈ {0, . . . , r -1}}, thus i + h(i, j), j + h(i, j) ∈ D(t) as required. Note that a standard LZ phrase is not a ∆-approximate phrase. Also, while the LZ phrase starting at each position (and thus also the LZ factorisation) is uniquely defined, there may be multiple different ∆-approximate phrases starting at each position. This also means that a single string can have multiple different ∆-approximate factorisations. The definitions of both standard and ∆-approximate LZ phrases are illustrated in Fig. 3.

The intuition behind the above definition is that constructing the ∆-approximate LZ factorisation becomes easier for larger values of ∆. In particular, for ∆ = n one phrase is enough. We formalise this in the following lemma, which is made more general for the purpose of obtaining the final result in this section. .y] and T [j..y], for i, j ∈ S, with no additional comparisons. By the properties of D(∆), for any i, j ∈ {x, x+1, . . . , y -∆+1} we have 0 ≤ h(i, j) < ∆ and i+h(i, j), j +h(i, j) ∈ S.

In this section we show how to implement the approach described in the previous section to work in O(n log σ) time. The main difficulty is in efficiently implementing the sparse suffix tree construction algorithm, and then computing a ∆-approximate factorisation. We first how to obtain an O(n log σ + n log * n) time algorithm that still uses only O(n log σ) comparisons, and then further improve its running time to O(n log σ).

Constructing Suffix Tree and ∆-Approximate Factorisation

To give an efficient algorithmic construction of the sparse suffix tree from Lemma 4.1, we will use a restricted version of LCEs, where a query ShortLCE x (i, j) (for any positive integer x) returns min(x, lce(i, j)). The following result was given by Gawrychowski et al. [START_REF] Gawrychowski | Faster longest common extension queries in strings over general alphabets[END_REF]: Lemma 5.1. (Lemma 14 in [START_REF] Gawrychowski | Faster longest common extension queries in strings over general alphabets[END_REF]) For a length-n string over a general unordered alphabet2 , a sequence of q queries ShortLCE 4 k i for i ∈ {1, . . . , q} can be answered online in total time O(n log * n + s) and O(n + q) comparisons3 , where s = q i=1 (k i + 1).

In the lemma, apart from the O(n log * n) time, each ShortLCE 4 k i query accounts for O(k i + 1) time. Note that we can answer the queries online, without prior knowledge of the number and length of the queries. Also, computing an LCE in a fragment T [x..y] of length m trivially reduces to a ShortLCE 4 ⌈log 4 m⌉ query on T . Thus, we have: Corollary 5.1. A sequence of q longest common extension queries on a fragment T [x..y] of length m over a general unordered alphabet can be answered in O(q log m) time plus O(n log * n) time shared by all invocations of the lemma. The number of comparisons is O(q), plus O(n) comparisons shared by all invocations of the lemma.

While constructing the sparse suffix tree, we will maintain a heavy-light decomposition using a rebuilding scheme introduced by Gabow [START_REF] Gabow | Data structures for weighted matching and nearest common ancestors with linking[END_REF]. Let L(u) denote the number of leaves in the subtree of a node u. We use the following recursive construction of a heavy-light decomposition: Starting from a node r (initially the root of the tree), we find the deepest descendant node e such that L(e) ≥ 5 6 L(r) (possibly e = r). The path p from the root r(p) = r to e(p) = e is a heavy path and any edge (u, v) on this path is such that L(v) ≥ 5 6 L(u), we call those edges heavy. As a consequence, a node u can have at most one child v such that (u, v) is heavy. For each edge (u, v) with u is on the heavy path and v is not, we recursively build a new heavy path construction starting from v.

When inserting a new suffix in our tree, we keep track of the insertion in the following way: for every root of a heavy path, we maintain I(u) the number of insertions made in the subtree of u since we built the heavy-light decomposition of this subtree. When I(u) ≥ 1 6 L(u) we recalculate the values of L(v) for all nodes v in the subtree of u and rebuild the heavy-light decomposition for the subtree of u.

This insures that, despite insertion, for any heavy path starting at node r and a node u on that heavy path, L(e) ≥ 2 3 L(r). When crossing a non heavy edge the number of nodes in the subtree reduces by a factor at least With those building blocks now clearly defined, we are ready to describe the construction of the sparse suffix tree. Proof. As in the proof of Lemma 4.1, we consider the insertion of a suffix T [i j ..y] into the sparse suffix tree with suffixes T

[i 1 ..y], T [i 2 ..y] • • • T [i j-1 ..y].
At all times, we maintain the heavy path decomposition. Additionally, we maintain for each heavy path a predecessor data structure, where given some length ℓ, we can quickly identify the deepest explicit node on the heavy path that spells a string of length at least ℓ. The data structure can, e.g., be a balanced binary search tree with insertion and search operations in O(log b) time (the final sparse suffix tree and thus each heavy path contains O(b) nodes). When rebuilding a subtree of the heavy path decomposition, we also have to rebuild the predecessor data structure for each of its heavy paths. Thus, rebuilding a size-q subtree takes O(q log b) time (each node is on exactly one heavy path and has to be inserted into one predecessor data structure), and the amortized insertion time increases from O(log m) to O(log m • log b). Whenever we insert a suffix, we make at most one node explicit, and thus have to perform at most one insertion into a predecessor data structure. The time for this is O(log b), which is dominated be the previous term.

When inserting T [i j ..y], we look for the node u corresponding to the longest common prefix between T [i j ..y] and the inserted suffixes, make u explicit if necessary and add a new leaf corresponding to T [i j ..y] attached to u. Let v be the current node (initialized by the root, and always an explicit node) and v 1 , • • • , v d be its (explicit) children. If there is a heavy edge (v, v a ) for 1 ≤ a ≤ d, let p be the corresponding heavy path. For each heavy path p, we store the label of one leaf (i.e., the starting position of one suffix) that is contained in the subtree of e(p). Thus, we can use Corollary 5.1 to compute the longest common extension between the the string spelled by e(p) and T [i j ..y]. Now we use the predecessor data structure on the heavy path to find the deepest (either explicit or implicit) node v ′ on the path that spells a prefix of T [i j ..y]. If v ′ is implicit, we make it explicit and add the leaf. If v ′ is explicit and v ′ ̸ = v, we use v ′ as the new current node and continue. Otherwise, it holds v ′ = v, i.e., the suffix does not belong to the subtree rooted in v a . In this case, we issue d LCE queries between T [i j ..y] and each of the strings spelled by the nodes v 1 , . . . , v d . This either reveals that we can continue using one of the v a as the new current node, or that we can create a new explicit node on some (v, v a ) edge and attach the leaf to it, or that we can simply attach a new leaf to v. Now we analyse the time spent while inserting one suffix. We spent O(b • log m • log b) total time time for inserting O(b) nodes into the dynamic heavy path decomposition and the predecessor data structures. In each step of the insertion process, we either (i) move as far as possible along some heavy path or (ii) move along some nonheavy edge. For (i), we issue one LCE query and one predecessor query. In the following proof, we use i 1 , i 2 , . . . , i b interchangeably to denote both the difference cover positions, as well as their corresponding leaves in the sparse suffix tree. Assume that the order of difference cover positions is

i 1 < i 2 < • • • < i b . First, we determine for each i k > i 1 , the position src(i k ) = i h and the length len(i k ) = lce(i h , i k ), where i h ∈ {i 1 , . . . , i k-1 } is a position that maximizes lce(i h , i k )
. This is similar to what was done in [START_REF] Fischer | Lempel-Ziv factorization powered by space efficient suffix trees[END_REF] for the LZ77 factorisation. We start by assigning labels from {1, . . . , b} to the nodes of the sparse suffix tree. A node has label k if and only of i k is its smallest descendant leaf. We assign the labels as follows. Initially, all nodes are unlabelled. We assign label 1 to each node on the path from i 1 to the root. Then, we process the remaining leaves i 2 , . . . , i b in increasing order. For each i k , we follow the path from i k to the root. We assign label k to each unlabelled node that we encounter. As soon as we reach a node that has already been labelled, say, with label h and string-depth ℓ, we are done processing leaf i k . It should be easy to see that i h is also exactly the desired index that maximizes lce(i h , i k ), and it holds lce(i h , i k ) = ℓ. Thus, we have found src(i k ) = i h and len(i k ) = ℓ. The total time needed is linear in the number of sparse suffix tree nodes, which is O(b).

Finally, we obtain a ∆-approximate LZ factorisation using src and len. The previously computed values can be interpreted as follows: i k could become the starting position of a length-len(i k ) tail (with previous occurrence at position src(i k )). For the ∆-approximate LZ factorisation, we will create the factors greedily in a left-toright manner. Assume that we already factorised T ′ [1..s -1], then the next phrase starts at position s, and thus the next tail starts within T ′ [s..s + ∆) (as a reminder, the head is by definition shorter than ∆). Let S = {i 1 , i 2 , . . . , i b } ∩ {s, . . . , s + ∆ -1}. If there is no i k ∈ S with i k + len(i k ) > s + ∆ -1, then the next phrase is simply T ′ [s.. min(|T |, s + ∆ -1)) with empty tail. Otherwise, the next phrase has (possibly empty) head T ′ [s..i k ) and tail T ′ [i k ..i k + len(i k )) (with previous occurrence src(i k )), where i k is chosen from S such that it maximizes i k + len(i k ). Creating the phrase in this way clearly takes O(|S|) time. Since the next phrase starts at least at position s + ∆ -1, none of the positions from S \ {s + ∆ -1} will ever be considered as starting positions of other tails. Thus, every i k is considered during the creation of at most two phrases, and the total time needed to create all phrases is O(b).

It remains to be shown that the computed factorisation is indeed a ∆-approximate LZ factorisation, i.e., if we output a phrase T ′ [s..e], then the unique (non-approximate) LZ phrase T ′ [s..e ′ ] starting at position s satisfies e ′ -1 ≤ e. First, note that for the created approximate phrases (except possibly the last phrase of T ) it holds s + ∆ -2 ≤ e. Assume e ′ < s + ∆, then clearly e ′ -1 ≤ e. Thus, we only have to consider e ′ > s + ∆ -1. Since T ′ [s..e ′ ] is an LZ phrase, there is some s ′ < s such that lce(s ′ , s) = e ′ -s. Let h be the constant-time computable function that defines the ∆-cover, and let i k ′ = s ′ + h(s ′ , s) and

i k = s + h(s ′ , s). Note that i k ′ ∈ {i 1 , i 2 , . . . , i k-1 } and i k ∈ {i 1 , i 2 , . . . , i b } ∩ {s, . . . , s + ∆ -1}. Therefore, it holds len(i k ) ≥ lce(i k ′ , i k ) = lce(s ′ , s) -h(s ′ , s) = (e ′ -s) -(i k -s) = e ′ -i k . While computing the ∆-approximate phrase T ′ [s.
.e], we considered i k as the starting positions of the tail, which implies e ≥ i k + len(i k ) -1 ≥ e ′ -1. Proof. We simply use Lemma 5.3 to compute the factorisation. In the first step, we have to construct the sparse suffix tree using the algorithm from Lemma 5.2. While this algorithm takes O(mσ log 2 m/ √ ∆) time, it should be easy to see that a more accurate time bound is O(md log 2 m/ √ ∆), where d is the maximum degree of any node in the suffix tree. If during construction the maximum degree of a node becomes σ + 1, we immediately stop and return that σ > σ. Otherwise, we finish the construction in the desired time. Now we can describe the algorithm that detects squares in O(n lg σ+n log * n) time and O(n lg σ) comparisons. We simply use the algorithm from Section 4, but use Lemma 5.4 instead of Lemma 4.6. Next, we analyse the time needed apart from the O(n log * n) time shared by all invocations of Lemma 5.4. Throughout the t th phase, we use For detecting squares, we still use Lemma 4.5, which as explained in Section 4 takes O(n) time and comparisons in total, plus additional O(Z) time, where Z is the number of approximate LZ factors considered during all invocations of the lemma. Since we apply the lemma to each approximate LZ factorisation exactly once, and by construction each factor has size at least ∆ thus Z = O(n/∆).

O(n • σ • log 2 (σ t )/ √ ∆) = O(n • (σ t ) 1/4 / log(σ t ) • log 2 (σ t )/ √ σ t ) = O(n log(σ t )/(σ t )
The last thing that remains to be shown is how to implement the bookkeeping of blocks, i.e., in each phase we have to efficiently deactivate block pairs as described at the end of Section 4. We maintain the block pairs in ⌈log log n⌉ bitvectors of total length O(n), where a set bit means that a block pair has been deactivated (recall that there are O(n) pairs in total). Bitvector t contains at position j the bit corresponding to block pair B j B j+1 = T [i..i + 2(σ t ) 2 ) with i = (σ t ) 2 • (j -1). Note that translating between i and j takes constant time. For each sufficiently long tail in phase t, we simply iterate over the relevant block pairs in phase t + 2 and deactivate them, i.e., we set the corresponding bit. This takes time linear in the number of deactivated blocks. Since there are O(n) block pairs, and each block pair gets deactivated at most a constant number of times, the total cost for this bookkeeping is O(n).

The number of comparisons is dominated by the O(n log σ) comparisons used when finishing the computation with Theorem 2.1. The only other comparisons are performed by Lemma 4.5, which we already bounded by O(n), and by LCE queries via Corollary 5.1. Since we ask O(n) such queries in total, the number of comparisons is also O(n). We have shown:

Lemma 5.5. The square detection algorithm from Section 4 can be implemented in O(n lg σ + n log * n) time and O(n log σ) comparisons.

Final Improvement

For our final improvement we need the notion of a string synchronising set introduced by Kempa and Kociumaka [START_REF] Kempa | String synchronizing sets: sublinear-time BWT construction and optimal LCE data structure[END_REF]. .n] when it satisfies the following conditions:

1. if T [i..i + 2τ ) = T [j..j + 2τ ), then i ∈ S holds if and only if j ∈ S (for i, j ∈ [1, n -2τ + 1]), 2. S ∩ [i, i + τ ) = ∅ if and only if the period of T [i..i + 3τ -2] is at most τ 3 (for i ∈ [1, n -3τ + 2]).
The first condition can be interpreted as saying that whether i ∈ S depends only on the string T [i..i + 2τ ). That is, a τ -synchronising set is obtained by selecting a set S of length-2τ strings, and then including in S the starting positions of all strings s ∈ S in T [1.

.n]. The second condition will not be relevant in our application, as we will always ensure that there are no periodic fragments. .y]| (with m = Θ(∆), as otherwise we are not required to detect anything). As in the previous section, the algorithm might detect that the size of the alphabet is larger than σ, and in such case we revert to the divideand-conquer algorithm. Because τ is sufficiently small, by adjusting the constants a (∆ + 3τ )-approximate LZ factorisation can be used instead of a ∆-approximate LZ factorisation in the approach described in the previous section, and this results in the promised O(n log σ) overall time complexity.

Initially, we only consider some fragments of T [x..y]. We say that T [i..i + 3⌊ √ ∆⌋) is a dense fragment if i ≡ 0 (mod ∆). We start by remapping the characters in all dense fragments that intersect T [x..y] to a linearly-sortable alphabet. This can be done in O(σ) time for each position by maintaining a list of the already seen distinct characters. For each position in a dense fragment, we iterate over the characters in the list, and possibly append a new character to the list if it is not already present. As soon as the size of the list exceeds σ, we terminate the procedure. Otherwise, we replace each character by its position in the list. Overall, there are O(m/ √ ∆) positions in the dense fragments of T [x..y], and thus the remapping takes O(mσ/ √ ∆) time. Next, we construct generalised suffix trees [START_REF] Gusfield | Algorithms on Strings, Trees, and Sequences -Computer Science and Computational Biology[END_REF] of all dense fragments and their reversals. Again, because we now work with a linearly-sortable alphabet this takes only O(m/ √ ∆) time [START_REF] Farach | Optimal suffix tree construction with large alphabets[END_REF]. We consider fragments of the form T [i • 2τ..(i + 1) • 2τ ) having non-empty intersection with T [x..y]. We call such fragments chunks. We note that there are O(m/ √ ∆) chunks, and their total length is O(m). For each chunk, we find its longest prefix

T [i • 2τ..i • 2τ + ℓ i ) and longest suffix T [(i + 1) • 2τ -r i ..(i + 1) • 2τ
) that occur in one of the dense fragments. This can be done efficiently by following the heavy path decomposition of the generalised suffix tree of all dense fragments and their reversals, respectively. On each current heavy path, we just naively match the characters as long as possible, and in case of a mismatch spend O(σ) time to descend to the appropriate subtree. The total time per chunk is thus O(σ log m) plus the lengths of the longest prefix and suffix. The former sums up to O(mσ log m/ √ ∆), and we will later show that the latter can be amortised by deactivating blocks on the lower levels.

The situation so far is that we have remapped the alphabet of all dense fragments to linearly-sortable, and for every chunk we know its longest prefix and suffix that occur in one of the dense fragments. We concatenate (i) all dense fragments, and (ii) all fragments of the form T

[i • 2τ -r i-1 ..i • 2τ + ℓ i ) (intersected with T [x.
.y]) while adding distinct separators in between to form a new string T ′ . We stress that, because we have remapped the alphabet of all dense fragments, and the found longest prefix and suffix of each chunk also occur in some dense fragment, T ′ is over linearly-sortable alphabet. The next step is to test square-freeness of T ′ . As we have remapped its alphabet to linearly-sortable, this takes only O(m/ √ ∆ + i (ℓ i + r i )) time by Theorem 2.2. We will later show that O( i (ℓ i + r i )) can be amortised by deactivated blocks on the lower levels. If there is a square in T ′ , due to the separators being distinct it must fully belong to a fragment of T [x..y], thus we can terminate the whole algorithm. Thus, from now on, we assume that T ′ is square-free. In particular, this implies that there are no fragments T ′ [i..i + 3τ -2] with period at most τ 3 there. We use Theorem 5.1 to build a τ -synchronizing set S of T ′ , for τ = √ ∆ = σt 8 . We observe that, for every i ∈ S such that T ′ [i..i + 2τ ) does not contain any separator symbol, we can find the corresponding position i ′ in T [x..y] such that T ′ [i..i + 2τ ) = T [i ′ ..i ′ + 2τ ). We create the truncated τ -synchronising set S ′ of T [x..y] by including all such i ′ for which T [i ′ ..i ′ + 2τ ) has an occurrence in a dense fragment (we note that the same i ′ might be included in S ′ due to more than one i, as the fragments concatenated to obtain T ′ are not disjoint in T [x..y]). To implement this efficiently, we first precompute for every position in T ′ its corresponding position in T [x..y] and the position of the nearest separator. This can be done in O(|T ′ |) time when constructing T ′ , and allows us to filter out positions i such that T ′ [i..i + 2τ ) does not contain any separator symbol. Next, we build the suffix tree ST of T ′ in O(|T ′ |) time. For each node of ST corresponding to a fragment of length at least 2τ , we precompute its unique ancestor (implicit or explicit) corresponding to a fragment of length 2τ . Additionally, for each explicit node of ST we precompute whether its corresponding string has an occurrence in a dense fragment of T . This can be done in a bottom-up traversal in O(|T ′ ) time, and allows us to complete the filtering.

Although we built S ′ by considering T ′ instead of T [x.

.y], it still has some properties of a string synchronising set of T [x..y].

Lemma 5.6. The set S ′ satisfies the following conditions:

1. For any i, j ∈ [x, y -2τ + 1], if T [i..i + 2τ ) = T [j..j + 2τ ) then i ∈ S ′ ⇐⇒ j ∈ S ′ . 2. For any i ∈ [x, y -∆ -τ + 1], it holds S ′ ∩ [i, i + ∆ + τ ) ̸ = ∅.

It holds |S

′ | = O(m/τ ).
Proof. First, by the construction of the truncated τ -synchronizing set, it holds i / ∈ S ′ for all the T [i..i + 2τ ) that do not have any occurrence in a dense fragment. Thus, we only have to consider the case where T [i..i + 2τ ) has an occurrence in a dense fragment. Note that the chunk boundary i

′ • 2τ with i ′ = i 2τ is contained in T [i..i + 2τ ). We included T [i ′ • 2τ -r i-1 ..i ′ • 2τ + ℓ i ) in T ′ ,
and since T [i..i + 2τ ) has an occurrence in a dense fragment it holds i ′ • 2τ -r i-1 ≤ i and i + 2τ ≤ i ′ • 2τ + ℓ i . Thus, T [i..i + 2τ ) has a corresponding fragment in T ′ . If there is another fragment T [j..j + 2τ ) = T [i..i + 2τ ), then T [j..j + 2τ ) has a corresponding fragment in T ′ by the same reasoning. This yields the claimed condition.

Second, let i ′ = i ∆ •∆ and consider the dense fragment T [i ′ ..i ′ +3τ ). It is included in T ′ , say as T ′ [i ′′ ..i ′′ +3τ ), and by the assumption on T ′ being square-free and property 2 of a τ -synchronising set there will be a position j ∈ S ∩ [i ′′ , i ′′ + τ ). Then, j has its corresponding position j ′ in S ′ ∩ [i ′ , i ′ + τ ) that is not filtered out when forming S ′ (because T [j ′ ..j ′ +2τ ) occurs inside the dense fragment T

[i ′ ..i ′ +3τ )). Finally, note that [i ′ , i ′ +τ ) ⊂ [i, i+∆+τ ) because of i ′ ∈ [i, i + ∆), and thus j ′ ∈ S ′ ∩ [i, i + ∆ + τ ).
Lastly, the length of T ′ is O(m). Since we used Theorem 5.1 to construct S, it holds |S| = O( m τ ). Each position in S contributes at most one position to S ′ , and thus

|S ′ | ≤ |S| = O( m τ ).
We now define a partial parsing of T [x..y] with a $ character appended at the end based on S ′ (in fact, the following would work for any set that satisfies the conditions from Lemma 5.6). Let i 1 < i 2 < . . . i k be all the positions in S ′ , that is, (i j , i j+1 ) ∩ S ′ = ∅ for every j = 1, 2, . . . , k -1. For every j = 1, 2, . . . , k -1, we create the phrase T [i j ..i j+1 + 2τ ). We add a last phrase T [i k ..y]$. We stress that consecutive phrases overlap by 2τ characters, and each phrase begins with a length-2τ fragment starting at a position in S ′ . This, together with property 1 of Lemma 5.6, implies the following useful property.

Observation 5.2. The set of distinct phrases is prefix-free.

We would like to construct the compacted trie T phrase of all such phrases, so that (in particular) we identify identical phrases. We first notice that each phrase begins with a fragment T [i j ..i j+2τ ) that has its corresponding occurrence in T ′ , and using the suffix tree of T ′ we can partition all phrases according to their prefixes of length 2τ . This gives us the top part of T phrase containing all such prefixes in O(m/ √ ∆) time, and for each phrase we can assume that we know the node of T phrase corresponding to its length-2τ prefix. Next, we iterate over the phrases, and insert them into T phrase using a dynamic heavy path decomposition as in Section 5.1. For each phrase T [i j ..i j+1 + 2τ ), we begin the insertion at the already known node corresponding to T [i j ..i j + 2τ ), and continue the insertion by following the heavy paths. On each heavy path, we naively match the characters as long as possible. The total time spent on maintaining the dynamic trie and its heavy path decomposition is O(m log m/ √ ∆), while the time to insert a single phrase T [i j ..i j+1 + 2τ ) is O(log m) plus the length of the longest prefix of T [i j + 2τ..i j+1 + 2τ ) equal to a prefix of T [i j ′ + 2τ..i j ′ +1 + 2τ ), for some j ′ < j. The former sums up to another O(m log m/ √ ∆), and we will later show that the latter can be amortised by deactivating blocks on the lower levels.

T phrase allows us to form metacharacters corresponding to the phrases, and transform T [x.

.y] into a string T parse of length O(m/ √ ∆) consisting of these metacharacters. We build a suffix tree S parse over this string over linearly-sortable metacharacters in O(m/ √ ∆) time. Next, we convert it into the sparse suffix tree S ′ parse of all suffixes T [i..j] as follows. Consider an explicit node u ∈ S parse with children v 1 , v 2 , . . . , v d , d ≥ 2. We replace u with the subtree T u of T parse induced by the leaves corresponding to the first metacharacters on the edges (u, v i ), for i = 1, 2, . . . , d, and connect every v i to the appropriate leaf of T u . This can be implemented in O(d) time, assuming constant-time lower common ancestor queries on T phrase [START_REF] Bender | The LCA problem revisited[END_REF] and processing the leaves from left to right with a stack, similarly as in the Cartesian tree construction algorithm [START_REF] Vuillemin | A unifying look at data structures[END_REF]. Overall, this sums up to O(m/ √ ∆). By following an argument from the proof of Lemma 5.3, S ′ parse allows us to determine, for every suffix T [i j ..y], its longest prefix equal to a prefix of some T [i ′ ..y] with i ′ < i j , as long as its length is at least 2τ . Indeed, in such case we must have i ′ ∈ S ′ by property 1 of Lemma 5.6, so in fact i ′ = i j ′ and it is enough to maximise the length of the common prefix with all earlier positions in S ′ , which can be done using S ′ parse . Thus, we either know that the length of this longest prefix is less than 2τ , or know its exact value (and the corresponding position i ′ ∈ S ′ ). We first check if the longest common prefix between T [e ′′ ..y] and any suffix starting at an earlier position is of length at least 2τ . If not, we simply set the head of the new phrase to be T [e..e ′′ + 2τ ) and the tail to be empty. Otherwise, we know the length ℓ of this longest prefix. We set the head of the new phrase to be T [e..e ′′ ) and the tail to be T [e ′′ ..e ′′ + ℓ). This takes constant time per phrase, and each phrase is of length at least τ , giving the claimed overall time complexity. It remains to argue correctness of every step.

Let T [e..s] be the longest LZ phrase starting at position e, to show that we obtain a valid (∆+3τ )-approximate phrase it suffices to show that s ≤ e ′′ + max(2τ, ℓ). Let the previous occurrence of T [e..s) be at position p < e. If s -e ′′ < 2τ then there is nothing to prove. Otherwise, T [e ′′ ..s) is a string of length at least 2τ that also occurs starting earlier at position p + e ′′ -e < e ′′ . Thus, we will correctly determine that ℓ ≥ 2τ , and find a previous occurrence of the string maximising the value of ℓ. In particular, we will have ℓ ≥ s -e ′′ as required.

To achieve the bound of Theorem 1.3, we now proceed as in Section 4.4, except that instead of Lemma 5.4 we use Lemma 5.7. This takes O(mσ log m/ √ ∆) for every T [x..y] with m = |T [x..y]|, however we need to additionally account for the additional comparisons used when computing the longest common prefixes and suffixes of every chunk, and inserting T [i j + 2τ..i j+1 + 2τ ) into T phrase . We observe that in both cases we can deactivate any block fully contained in the corresponding fragment of the input string. For T [i • 2τ..i • 2τ + ℓ i ) and T [(i + 1) • 2τ -r i ..(i + 1) • 2τ ) this follows because we test square-freeness of these fragments anyway in the current phase. For the longest prefix of T [i j + 2τ..i j+1 + 2τ ) equal to T [i j ′ + 2τ..i j ′ +1 + 2τ ), for some j ′ < j, this follows because such fragment cannot contain the leftmost occurrence of a square. There are O(m/ √ ∆) chunks and phrases. We can afford to spend O( √ ∆) comparisons for each phrase because then the total number of comparisons sums to O(n) over all phases. If a chunk or phrase contributes x = Ω( 4 √ ∆) comparisons, then we explicitly deactivate the block pairs in phase t+3 that are entirely contained in the corresponding fragment. Block pairs in phase t + 3 are of length O( 4 √ ∆), and thus we deactivate O(x) positions. Therefore, the comparisons performed when inserting chunks and phrases into their respective tries in all phases sums to O(n).

Theorem 2 . 1 .

 21 Testing square-freenes of T [1..n] over a general alphabet can be implemented in O(n log n) time and comparisons.

Theorem 2 . 2 .

 22 Testing square-freenes of T [1..n] over a general ordered alphabet can be implemented in O(n) time. Lempel-Ziv factorisation. The unique LZ phrase starting at position s is a fragment T [s..e] such that T [s..(e -1)] occurs at least twice in T [1..(e -1)] and T [s..e] occurs only once in T [1..e]. The Lempel-Ziv factorisation

Figure 1 :

 1 Figure 1: Example conflict graph of the adversary described in Section 3.2. The alphabet {0, . . . , 15} is of size σ = 16. The blocks are of length σ 4 = 4.The gray nodes are exactly the starting positions of the blocks and contain the symbols of the ternary Thue-Morse sequence v = 2, 1, 0, 2, 0, 1, 2, . . . , which is square-free. We assume that the colored nodes were colored in the following order: 2, 6, 8, 7, 15, 16, 14. At the time of coloring node 8, we had to avoid colors 0, 1, 2 (because they are reserved for the separator positions), 3 (because the adjacent node 2 already has color 2), and 4 (because node 6 is in the same block and already has color 4). The algorithm has not eliminated all squares yet. For example, nodes 10 and 11 with[START_REF] Bender | The LCA problem revisited[END_REF][START_REF] Berstel | Partial words and a theorem of Fine and Wilf[END_REF] / ∈ E are adjacent to nodes of colors {3, 6, 5} ∪ {5, 3, 4}. Thus, any of the colors {0, 1, 2} ∪ {7, . . . , 15} can be assigned to both nodes, enforcing the square T[10..11]. As visualized on the right, an edge of length ℓ eliminates at most ℓ squares.

4 .

 4 Each comparison may increase the degree of two nodes by one. Thus, the colored nodes account for at least σk-5n 8comparisons. There are k non-overlapping maximal colorless ranges of nodes, namely {c i + 1, . . . , c i+1 -1} for 1 ≤ i ≤ k with auxiliary value c k+1 = n + 1. According to Lemma 3.1, each respective range accounts for e i = ⌊mi/2⌋ ℓ=1 mi-2ℓ+1 ℓ

Lemma 4 . 1 .

 41 The sparse suffix tree containing any b suffixes T [i 1 ..n], . . . , T [i b ..n] of T [1..n] can be constructed using only O(bσ log b) comparisons plus O(n) comparisons shared by all invocations of the lemma. Proof. We maintain a union-find structure over the positions of T [1..n]. Initially, each position is in a separate component. Before issuing a query T [x]?

Figure 2 :T

 2 Figure 2: Positions in a ∆-difference cover.

Figure 3 :

 3 Figure 3: Illustration of the definition of a LZ-phrase and a ∆-approximate phrase.

4. 2

 2 Detecting Squares with a ∆-Approximate LZ Factorisation A crucial notion in our algorithm is the following variation on the standard Lempel-Ziv factorisation: Definition 4.1. (∆-approximate LZ factorisation) For a positive integer parameter ∆, the fragment T [s..e] is a ∆-approximate LZ phrase if it can be split into a head and a tail T [s..e] = head(T [s..e])tail(T [s..e]) such that |head(T [s..e])| < ∆ and additionally • tail(T [s..e]) is either empty or occurs at least twice in T [1..e], and • the unique (standard) LZ phrase T [s..e ′ ] starting at position s satisfies e ′ -1 ≤ e. In a ∆-approximate LZ factorisation T = b 1 b 2 . . . b z , each factor b i is a ∆-approximate phrase T [s..e] with s = 1 + i-1 j=1 |b j | and e = i j=1 |b j |.

Lemma 4 . 3 .

 43 For any parameter ∆ ∈ [1, m], a ∆-approximate LZ factorisation of any fragment T [x..y] of length m can be computed with O(mσ log m/ √ ∆) comparisons plus O(n) comparisons shared by all invocations of the lemma. Proof. By Lemma 4.2, there exists a ∆-cover D(∆) of {1, . . . , n} with size O(n/ √ ∆). Let S = D(∆) ∩ {x, x + 1, . . . , y}. Let S = {i 1 , i 2 , . . . , i b }. It is straightforward to verify that the construction additionally guarantees b = O(m/ √ ∆). We apply Lemma 4.1 on the suffixes T [i 1 ..n], . . . , T [i b ..n] to obtain their sparse suffix tree T with O(bσ log b) comparisons plus O(n) comparisons shared by all invocations of the lemma. T allows us to obtain the longest common prefix of any two fragments T [i.

5 6Observation 5 . 1 .

 551 which leads to the following property: The path from any node to the root crosses at most O(log m) heavy paths.Additionally, rebuilding a subtree of size s takes O(s) time and adding a suffix T [i j ..y] to the tree increases I(r) for each path p from the root r to the new leaf. Those are at most O(log m) nodes and thus maintaining the heavy path decomposition takes amortized time O(log n) per insertion.

Lemma 5 . 2 .

 52 The sparse suffix tree containing any b suffixes T [i 1 ..y], . . . , T [i b ..y] of T [x..y] with m = |T [x..y]| can be constructed using O(bσ log b log m) time plus O(n log * n) time shared by all invocations of the lemma.

  For (ii) we issue O(σ) LCE queries. Due to Observation 5.1, both (i) and (ii) happen at most O(log b) times per suffix. Thus, for all suffixes, we perform O(b log b) predecessor queries and O(bσ log b) LCE queries. The total time is O(b log 2 b) for predecessor queries, and O(bσ log b log m) for LCE queries (apart from the n log * n time shared by all invocations of Corollary 5.1). Lemma 5.3. For any parameter ∆ ∈ [1, m], a ∆-approximate LZ factorisation of any fragment T [x..y] of length m can be computed in O(mσ log 2 m/ √ ∆) time plus O(n log * n) time shared by all invocations of the lemma. Proof. Let T ′ = T [x..y], and let {i 1 , i 2 , . . . , i b } be a ∆-cover of {1, . . . , m}, which implies b = Θ(m/ √ ∆). We obtain a sparse suffix tree of the suffixes T ′ [i 1 ..m], . . . , T ′ [i b ..m], which takes O(bσ log b log m) ⊆ O(mσ log 2 m/ √ ∆) time according to Lemma 5.2, plus O(n log * n) time shared by all invocations of the lemma. Now we compute a ∆-approximate LZ factorisation of T ′ from the spare suffix tree in O(b) time.

Lemma 5 . 4 .

 54 There is an algorithm that, given any parameter ∆ ∈ [1, m], estimate σ and fragment T [x..y] of length m, takes O(mσ log 2 m/ √ ∆) time plus O(n log * n) time shared by all invocations of the lemma, and either computes a ∆-approximate LZ factorisation of T [x..y] or determines that σ > σ.

Definition 5 . 1 .

 51 Consider a string T [1..n] and a parameter τ≤ n 2 . A set S ⊆ [1, n -2τ + 1] is a τ -synchronising set of T [1.

Theorem 5 . 1 .

 51 (Proposition 8.10 in[START_REF] Kempa | String synchronizing sets: sublinear-time BWT construction and optimal LCE data structure[END_REF]) Given a string T [1..n] over linearly-sortable alphabet and a param-eter τ ≤ n 2 , we can construct a τ -synchronising set of size O(n/τ ) in O(n) time.The goal of this section is to show how to, given a parameter ∆ and estimate σ of the alphabet size, find a (∆ + 3τ )-approximate LZ factorisation of any fragment T [x..y] in O(mσ/ √ ∆) time, where τ = ⌊ √ ∆⌋ and m = |T [x.

Lemma 5 . 7 .

 57 For any parameter ∆ ∈ [1, m] and estimate σ of the alphabet size, a (∆ + 3τ )-approximate LZ factorisation of any fragment T [x..y] can be computed in O(m/ √ ∆) time with m = |T [x..y]| (assuming the preprocessing described earlier in this section). Proof. Let e ∈ [x, y] and suppose we have already constructed the factorisation of T [x..e -1] and are now trying to construct the next phrase. Let e ′ be the next multiple of ∆, we have that e ′ -e < ∆ and T [e ′ ..e ′ + 3⌊ √ ∆⌋ is a dense substring. Thus, by property 2 of Lemma 5.6 we have S ′ ∩ [e ′ , e ′ + τ ) ̸ = ∅. Let e ′′ ∈ S ′ ∩ [e ′ , e ′ + τ ).

  1/4 ) comparisons to construct all the ∆-approximate factorisations. As before, if at any time we discover that σ > (σ t ) 1/4 / log(σ t ), then we use Theorem 2.1 to finish the computation in O(n lg σ t ) = O(n log σ) time. Until then (or until we finished all ⌈log log n⌉ phases), we use O( t ′ t=0 n log(σ t )/(σ t ) 1/4 ) time, and by Corollary 4.1 this is O(n).

In the descent, if all children are sorted according to their subtree size, the number of comparisons decreases to O(b(σ/ log σ) log b), but this appears irrelevant for our final algorithm.

Lemma 14 in [39] does not explicitly mention that it works for general unordered alphabet. However, the proof of the lemma relies solely on equality tests.

Lemma 14 in [39] does not explicitly mention that it requires O(n + q) comparisons. However, they use a union-find approach where there can be at most O(n) comparisons with outcome "equal", and each LCE query performs only one comparison with outcome "not-equal", similarly to what we describe in the proof of Lemma

4.1.

Partially supported by the German Research Association (DFG) within the Collaborative Research Center SFB 876, project A6. † Institute of Computer Science, University of Wroc law, Poland. Partially supported by the grant ANR-20-CE48-0001 from the French National Research Agency (ANR). ‡ DI/ENS, PSL Research University, IRISA Inria Rennes, France. Partially supported by the grant ANR-20-CE48-0001 from the French National Research Agency (ANR).

We compute the ∆-approximate LZ factorisation of T [x..y] phrase-by-phrase. Denoting the remaining suffix of the whole T [x..y] by T [x ′ ..y], we need to find x ′ ≤ y ′ ≤ y such that T [x ′ ..y ′ ] is a ∆-approximate phrase. This is done as follows. We iterate over every x ′ ≤ x ′′ < x ′ + ∆ such that x ′′ ∈ S. For every such x ′′ , we consider every x ≤ a ′ < x ′ such that a ′ ∈ S, and compute the length ℓ of the longest common prefix of T [x ′′ ..y] and T [a ′ ..y]. Among all such x ′′ , a ′ we choose the pair that results in the largest value of x ′′ -x ′ + ℓ -1 and choose the next phrase to be T [x ′ ..(x ′′ + ℓ -1)], with the head being T [x ′ ..(x ′′ -1)] and the tail T [x ′′ ..(x ′′ + ℓ) -1]. Finally, if there is no such pair, or the value of x ′′ -x ′ + ℓ -1 corresponding to the found pair is less than ∆ -2, we take the next phrase to be T [x ′ .. min{x ′ + ∆ -1, y}] (with empty tail). Selecting such a pair requires no extra comparisons, as for every x ′′ , a ′ ∈ S we can use the sparse suffix tree to compute ℓ. While it is clear that the generated ∆-approximate phrase has the required form, we need to establish that it is sufficiently long.

Let T [x ′ ..y ′′ ] be the (unique) phrase being a prefix of T [x ′ ..y]. If y ′′ < x ′ + ∆ -1 then we only need to ensure that the generated ∆-approximate phrase is of length at least min{∆ -1, y -x ′ + 1}, which is indeed the case. Therefore, it remains to consider the situation when

is a phrase this is well defined). Thus, T [a..b] = T [x ′ ..(y ′′ -1)] and a < x ′ . Because y ′′ ≥ x ′ +∆-1 and y ′′ ≤ y, as explained above 0 ≤ h(a, x ′ ) < ∆ and a+h(a, x ′ ), x ′ +h(a, x ′ ) ∈ S. We will consider

so when considering this pair we will obtain ℓ ≥ |T [x ′′ ..(y ′′ -1)]|. Thus, for the found pair we will have x ′′ + ℓ -1 ≥ y ′′ -1 as required in the definition of a ∆-approximate phrase.

Next, we show that even though the ∆-approximate LZ factorisation does not capture all distinct squares, as it is the case for the standard LZ factorisation, it is still helpful in detecting all sufficiently long squares. A crucial component is the following property of the ∆-approximate LZ factorisation. Proof. Assume that all tails that intersect T [s + ℓ..s + 2ℓ -1] are of length less than ℓ 4 , then the respective phrases of these tails are of length at most ℓ 4 + ∆ -1 (because each head is of length less than ∆). This means that T [s + ℓ..s + 2ℓ -1] intersects at least ℓ/( ℓ 4 + ∆ -1) ≥ ℓ/( ℓ 2 -1) = 3 phrases. Thus there is some phrase b i = T [x..y] properly contained in T [s + ℓ..s + 2ℓ -1], formally s + ℓ < x ≤ y < s + 2ℓ -1. However, this contradicts the definition of the ∆-approximate LZ factorisation because T [x..s + 2ℓ] is the prefix of a standard LZ phrase (due to T [x..s + 2ℓ -1] = T [x -ℓ..s + ℓ -1]), and the ∆-approximate phrase b i = T [x..y] must satisfy y ≥ s + 2ℓ -1. The contradiction implies that T [s + ℓ..s + 2ℓ -1] intersects a tail of length at least ℓ 4 ≥ ∆. Proof. We consider each phrase

Due to the intersection, it holds a 2 ≤ s + 2ℓ -1 and a 3 ≥ s + ℓ. Thus, when processing b i and applying Lemma 2.1, the starting position of x 1 and x 2 satisfies a 2 -8k ≤ s+2ℓ-1-8 ℓ 4 = s-1, while the end position of y 1 and y 2 satisfies a 3 +4k -1 ≥ s+ℓ+4 ℓ 4 -1 = s+2ℓ-1. Therefore, the square is entirely contained in the respective fragments corresponding to x 1 y 1 and x 2 y 2 . If s < a 2 ≤ s + 2ℓ -1, we find the square with our choice of x 1 and y 1 . If s < a 3 ≤ s + 2ℓ -1, we find the square with our choice of x 2 and y 2 . Otherwise, T [s..s + 2ℓ -1] is entirely contained in tail T [a 2 ..a 3 ], and we find another occurrence of the square further to the left.

Simple Algorithm for Detecting Squares

Now we have all the tools to introduce our simple method for testing square-freeness of T [1..n] using O(n(log σ + log log n)) comparisons, assuming that σ is known in advance. Let ∆ = (σ log n) 2 . We partition T [1.

.n] into blocks of length 8∆, and denote the k th block by B k . A square of length at most 8∆ can be found by invoking Theorem 2.1 on B 1 B 2 , B 2 B 3 , and so on. This takes O(∆ log ∆) = O(∆(log σ + log log n)) comparisons for each pair of adjacent blocks, or O(n(log σ + log log n)) comparisons in total. It remains to test for squares of length exceeding 8∆. This is done by first invoking Lemma 4.3 to compute a ∆-approximate LZ factorisation of T [1..n] with O(nσ log n/ √ ∆) = O(n) comparisons, and then using Lemma 4.5, which adds another O(n) comparisons. The total number of comparisons is dominated by the O(n(log σ + log log n)) comparisons needed to apply Theorem 2.1 to the block pairs.

Improved Algorithm for Detecting Squares

We are now ready to describe the algorithm that uses only O(n log σ) comparisons without knowing the value of σ. Intuitively, we will proceed in phases, trying to "guess" the value of σ. We first observe that Lemma 4.3 can be extended to obtain the following. Proof. We run the procedure described in the proof of Lemma 4.3 and keep track of the number of comparisons with negative answer. As soon as it exceeds O(mσ log m/ √ ∆) (where the constant follows from the complexity analysis) we know that necessarily σ > σ, so we can terminate. Otherwise, the algorithm obtains a ∆-approximate LZ factorisation with O(mσ log m/ √ ∆) comparisons.

Comparisons with positive answer are paid for globally. Now we describe how to find any square using O(n lg σ) comparisons. We define the sequence σ t = 2 2 ⌈log log n⌉-t , for t = 0, 1, . . . , ⌈log log n⌉. We observe that σ t-1 = (σ t ) 2 , and proceed in phases corresponding to the values of t. In the t th phase we are guaranteed that any square of length at least (σ t ) 2 has been already detected, thus it is enough to consider squares of length less than (σ t ) 2 . We partition the whole T [1.

.n] into blocks of length (σ t ) 2 , and denote the k th block by B k . A square of length less than (σ t ) 2 is fully contained within some two consecutive blocks B i B i+1 , hence we consider each such pair B 1 B 2 , B 2 B 3 , and so on. We first apply Lemma 4.6 with ∆ = σ t /8 and σ = (σ t ) 1/4 / log(σ t ) to find an (σ t /8)-approximate LZ factorisation of the corresponding fragment of T [1..n], and then use Lemma 4.5 to detect squares of length at least σ t . We cannot always afford to apply Lemma 4.5 to all block pairs. Thus, we have to deactivate some of the blocks, which we explain when analysing the number of comparisons performed by the algorithm. If any of the calls to Lemma 4.6 in the current phase detects that σ > σ, we switch to applying Theorem 2.1 on every pair of blocks B i B i+1 of the current phase and then terminate the whole algorithm.

We now analyse the total number of comparisons, ignoring the O(n) comparisons shared by all invocations of Lemma 4.6. Throughout the t th phase, we use

) comparisons to construct the ∆-approximate factorisations (using Lemma 4.6) until we either process all pairs of blocks or detect that σ > (σ t ) 1/4 / log(σ t ). In the latter case, we finish off the whole computation with O(n log(σ t )) comparisons (using Theorem 2.1), and by assumption on σ this is O(n log σ) as required. Until this happens (or until we reach phase t = ⌈log log n⌉ -3 where σ t ≤ 256), we use O(

t=0 n/(σ t ) 1/4 ) comparisons to construct the ∆-approximate factorisations, for some 0 ≤ t ′ ≤ ⌈log log n⌉. To analyse the sum, we need the following bound (made more general for the purpose of the next section). Lemma 4.7. For any 0 ≤ x ≤ y and c ≥ 0 we have

Proof. We observe that the sequence of exponents 2 i is strictly increasing from i = 0, hence

is a series of positive terms, we thus use Alembert's ratio test

(i+1) c which tends to 1 2 when i goes to the infinity, thus the series converges to a constant.

Corollary 4.1. For any 0 ≤ t ′ ≤ ⌈log log n⌉, it holds

Proof. We have to show that t ′ t=0 n log c (σ t )/(σ t ) 1/4 ) = O(n) for any constant c ≥ 0. We achieve this by splitting the sum and applying Lemma 4.7.

Thus, all invocations of Lemma 4.6 cause O(

Deactivating Block Pairs It remains to analyse the number of comparisons used by Lemma 4.5 throughout all phases. As mentioned earlier, we cannot actually afford to apply Lemma 4.5 to all block pairs. Thus, we introduce a mechanism that deactivates some of the pairs. First, note that there are O(

t=0 n/(σ t ) 1/4 ) = O(n) block pairs in all phases. For each pair, we store whether it has been deactivated or not, where being deactivated roughly means that we do not have to investigate the pair because it does not contain a leftmost distinct square. For each block pair B i B i+1 in the current phase t, we first check if it has been marked as deactivated. If not, we also check if it has been implicitly deactivated: if any of the two pairs from the previous phase that contain B i B i+1 are marked as deactivated. If B i B i+1 has been implicitly deactivated, then we mark it as deactivated and do not apply Lemma 4.6 and Lemma 4.5 (the implicit deactivation serves the purpose of propagating the deactivation to all later phases). Note that if some position of the string is not contained in any active block pairs in some phase, then it is also not contained in any active block pairs in all later phases. This is because it always holds σ t-1 = (σ t ) 2 (with no rounding required), which guarantees that block boundaries of earlier phases do not intersect blocks of later phases.

We only apply Lemma 4.6 and then Lemma 4.5 to B i B i+1 if the pair has neither explicitly nor implicitly been deactivated. When applying Lemma 4.5, a tail T [a..a + ℓ) contributes O(ℓ) comparisons if ℓ ≥ ∆ = σ t /8 (and otherwise it contributes no comparisons). Note that if we finish the phase without detecting a square, then T [a..a + ℓ) has a previous occurrence T [a ′ ..a ′ + ℓ) = T [a..a + ℓ) with a ′ + ℓ ≤ a, i.e., the occurrences do not overlap (if the only previous occurrence is overlapping, then T [a ′ ..2a -a ′ ) is a square that is detected when applying Lemma 4.5). Thus we can assume that there is a previous non-overlapping occurrence of T [a..a + ℓ). It follows that any block pair (of any phase) entirely contained in T [a..a + ℓ) occurs somewhere before B i B i+1 in the string, and thus such block pairs can be deactivated.

The mechanism used for deactivation works as follows. Let T [a..a+ℓ) be a tail contributing O(ℓ) comparisons with ℓ ≥ ∆ = σ t /8 in phase t. We mark all blocks of phase t + 2 that are entirely contained in T [a..a + ℓ) as deactivated. Note that blocks in phase t+2 are of length √ σ t , and consider the fragment T [a+2 √ σ t ..a+ℓ-2 √ σ t ).

In phase t + 2, and by implicit deactivation in all later phases, this fragment only contains or overlaps block pairs that have been deactivated. Thus, after phase t + 1, we will never inspect any of the symbols in T [a + 2 √ σ t ..a + ℓ -2 √ σ t ) again. We say that tail T [a..a + ℓ) deactivated the fragment of length ℓ -4 √ σ t = Ω(ℓ), which is positive until phase t = ⌈log log n⌉ -3 because σ t > 256. Since the number of deactivated positions is linear in the number of comparisons that the tail contributes to Lemma 4.5, it suffices to show that each position gets deactivated at most a constant number of times. In a single phase, any position gets deactivated at most twice. This is because the tails of each factorisation do not overlap by definition, but the tails of the two factorisations of adjacent block pairs B i B i+1 and B i+1 B i+2 can overlap. If a position gets deactivated for the first time in phase t, then (as explained earlier) we will not consider it in any of the phases t ′ ≥ t + 2. Thus, it can only be that we deactivate the position again in phase t + 1, but not in any later phases. In total, each position gets deactivated at most four times. We have shown:

Theorem 1.2. Testing square-freenes of a length-n string that contains σ distinct symbols from a general unordered alphabet can be done with O(n log σ) comparisons.