Lorraine A K Ayad
email: lorraine.ayad@kcl.ac.uk

Giulia Bernardini
email: giulia.bernardini@unimib.it

Roberto Grossi
email: grossi@di.unipi.it

Costas S Iliopoulos
email: c.iliopoulos@kcl.ac.uk

Nadia Pisanti
email: pisanti@di.unipi.it

Solon P Pissis
email: solon.pissis@cwi.nl

Giovanna Rosone
email: giovanna.rosone@unipi.it

Longest Property-Preserved Common Factor: a New String-Processing Framework

Keywords: square-free factors, periodic factors, palindromic factors

We introduce a new family of string processing problems. Given two or more strings, we are asked to compute a factor common to all strings that preserves a specific property and has maximal length. We consider three fundamental string properties: square-free factors, periodic factors, and palindromic factors under three different settings, one per property. In the first setting, we are given a string x and we are asked to construct a data structure over x answering the following type of online queries: given a string y, find a longest square-free factor common to x and y. In the second setting, we are given k strings and an integer 1 < k ≤ k and we are asked to find a longest periodic factor common to at least k strings. In the third one, we are given two strings and we are asked to find a longest palindromic factor common to the two strings. We present linear-time solutions for all settings.

Introduction

In the longest common factor problem, also known as the longest common substring problem, we are given two strings x and y, each of length at most n, and we are asked to find a maximal-length string occurring in both x and y. This is a classical and well-studied problem in computer science arising from different practical scenarios. It can be solved in O(n) time and space [START_REF] Hui | Color set size problem with applications to string matching[END_REF][START_REF] Gusfield | Algorithms on Strings, Trees, and Sequences -Computer Science and Computational Biology[END_REF] (see also [START_REF] Kociumaka | Sublinear space algorithms for the longest common substring problem[END_REF][START_REF] Starikovskaya | Time-space trade-offs for the longest common substring problem[END_REF][START_REF] Federico | Suffix tree characterization of maximal motifs in biological sequences[END_REF]). Recently, the same problem has been extensively studied under distance metrics; that is, the sought factors, one from x and one from y, must be at distance at most k and have maximal length. We refer the interested reader to [START_REF] Charalampopoulos | Linear-time algorithm for long LCF with k mismatches[END_REF][START_REF] Thankachan | A provably efficient algorithm for the k -mismatch average common substring problem[END_REF][START_REF] Thankachan | Algorithmic framework for approximate matching under bounded edits with applications to sequence analysis[END_REF][START_REF] Ayad | Longest common prefixes with k-errors and applications[END_REF][START_REF] Peterlongo | Lossless filter for finding long multiple approximate repetitions using a new data structure, the bi-factor array[END_REF][START_REF] Peterlongo | Lossless filter for multiple repetitions with Hamming distance[END_REF] and to references therein.

In this paper we initiate a new related line of research. We are given two or more strings and our goal is to compute a factor common to all strings that preserves a specific property and has maximal length. An analogous line of research was introduced in [START_REF] Chowdhury | Computing a longest common palindromic subsequence[END_REF]. The goal is to compute a subsequence (rather than a factor) common to all strings that preserves a specific property and has maximal length. Specifically, in [START_REF] Chowdhury | Computing a longest common palindromic subsequence[END_REF][START_REF] Bae | On finding a longest common palindromic subsequence[END_REF][START_REF] Inenaga | A hardness result and new algorithm for the longest common palindromic subsequence problem[END_REF], the authors considered computing a longest common palindromic subsequence and in [START_REF] Inoue | Computing longest common square subsequences[END_REF] computing a longest common square subsequence. Such algorithms can be employed by sequence comparison applications where, for example, common structural characteristics of the sequences imply common functionality [START_REF] Chew | Scoring schemes of palindrome clusters for more sensitive prediction of replication origins in herpesviruses[END_REF].

In what follows, we consider three fundamental string properties: squarefree factors, periodic factors, and palindromic factors [START_REF] Lothaire | Applied Combinatorics on Words, Encyclopedia of Mathematics and its Applications[END_REF] under three different settings, one per property. In the first setting, we are given a string x and we are asked to construct a data structure over x answering the following type of online queries: given a string y, find a longest square-free factor common to x and y. In the second setting, we are given k strings and an integer 1 < k ≤ k and we are asked to find a longest periodic factor common to at least k strings. In the third one, we are given two strings and we are asked to find a longest palindromic factor common to the two strings. We present linear-time solutions for all settings: in Section 2 for square-free factors; in Section 3 for periodic factors; and in Section 4 for palindromic factors. We conclude this paper and discuss these perspectives in Section 5.

A partial (without the third setting for palindromic factors) and preliminary version of this paper appeared in [START_REF] Ayad | Longest property-preserved common factor[END_REF], where we anticipated that our Longest Property-Preserved Common Factor framework could have been applied to other string properties or settings. Indeed, meanwhile in [START_REF] Kai | On longest common property preserved substring queries[END_REF] the authors introduced and solved several new problems within this framework: finding (online) a longest common factor that is a square, or periodic, or a Lyndon string. Moreover, in the same paper ( [START_REF] Kai | On longest common property preserved substring queries[END_REF]), the authors present an independent online algorithm for the third setting we introduce here: their query bound is O(|y| log |Σ|) where Σ is the alphabet (which becomes O(|y|) for constant-sized alphabets). Moreover, in [START_REF] Kai | On longest common property preserved substring queries[END_REF], for all string properties, the algorithms are extended to the setting of k given strings that are preprocessed in linear time to allow for a query that takes a string and an integer k and computes a longest common (to k of the input strings) property-preserved factor in linear time.

Definitions and Notation

An alphabet Σ is a non-empty finite ordered set of letters of size σ = |Σ|. In this work we consider that σ = O(1) or that Σ is a linearly-sortable integer alphabet. A string x on an alphabet Σ is a sequence of elements of Σ. The set of all strings on an alphabet Σ, including the empty string ε of length 0, is denoted by Σ * . For any string x, we denote by x[i . . j] the factor (sometimes called substring) of x that starts at position i and ends at position j. In particular, x[0 . . j] is the prefix of x that ends at position j, and x[i . . |x| -1] is the suffix of x that starts at position i, where |x| denotes the length of x. A string uu, u ∈ Σ + , is called a square. A square-free string is a string that does not contain a square as a factor.

A period of x[0 . . |x| -1] is a positive integer p such that x[i] = x[i + p] holds for all 0 ≤ i < |x| -p. The smallest period of x is denoted by per(x). String u is called periodic if and only if per(u) ≤ |u|/2. A run of a string x is an interval [i, j] such that for the smallest period p = per(x[i . . j]) it holds that 2p ≤ j -i + 1 and the periodicity cannot be extended to the left or right, i.e., i = 0 or x

[i -1] = x[i + p -1], and, j = |x| -1 or x[j -p + 1] = x[j + 1].
We denote the reversal of x by string x R , i.e.

x R = x[|x|-1]x[|x|-2] . . . x[0]
. A string p is said to be a palindrome if and only if p = p R . In other words, a palindrome is a string that reads the same forward and backward, i.e. a string p is a palindrome if p = yay R where y is a string, y R is the reversal of y and a is either a single letter or the empty string. If factor x[i . . j], 0 ≤ i ≤ j ≤ n -1, of a string x of length n is a palindrome, then i+j 2 is the center of x[i . . j] in x and j-i+1 2 is the radius of x[i . . j]. In this case, x[i . . j] is called a palindromic factor of x, and it is said to be a maximal palindrome if there is no other palindrome in x with center i+j 2 and larger radius. Hence x has exactly 2n -1 maximal palindromes. A maximal palindrome p of x can be encoded as a pair (c, r), where c is the center of p in x and r is the radius of p.

Algorithmic Toolbox

The maximum number of runs in a string of length n is less than n [START_REF] Bannai | The "runs" theorem[END_REF], and, moreover, all runs can be computed in O(n) time [START_REF] Kolpakov | Finding maximal repetitions in a word in linear time[END_REF][START_REF] Bannai | The "runs" theorem[END_REF].

The suffix tree ST(x) of a non-empty string x of length n is a compact trie representing all suffixes of x. ST(x) can be constructed in O(n) time [START_REF] Farach | Optimal suffix tree construction with large alphabets[END_REF]. We can analogously define and construct the generalised suffix tree GST(x 0 , x 1 , . . . , x k-1 ) for a set of k strings. We assume the reader is familiar with these data structures.

The matching statistics capture all matches between two strings x and y [START_REF] Chang | Sublinear approximate string matching and biological applications[END_REF]. More formally, the matching statistics of a string y[0 . . |y| -1] with respect to a string x is an array [START_REF] Gusfield | Algorithms on Strings, Trees, and Sequences -Computer Science and Computational Biology[END_REF][START_REF] Belazzougui | Indexed matching statistics and shortest unique substrings[END_REF][START_REF] Federico | Suffix tree characterization of maximal motifs in biological sequences[END_REF].

MS y [0 . . |y| -1], where MS y [i] is a pair ( i , p i ) such that (i) y[i . . i + i -1] is the longest prefix of y[i . . |y| -1] that is a factor of x; and (ii) x[p i . . p i + i -1] = y[i . . i + i -1]. Matching statistics can be computed in O(|y|) time for σ = O(1) by using ST(x)
Given a rooted tree T with n leaves coloured from 0 to k -1, 1 < k ≤ n, the colour set size problem consists of finding, for each internal node u of T , the number of different leaf colours in the subtree rooted at u. In [START_REF] Hui | Color set size problem with applications to string matching[END_REF], the author presents an O(n)-time solution to this problem.

In the weighted ancestor problem, introduced in [START_REF] Farach | Perfect hashing for strings: Formalization and algorithms[END_REF], we consider a rooted tree T with an integer weight function µ defined on the nodes. We require that the weight of the root is zero and the weight of any other node is strictly larger than the weight of its parent. A weighted ancestor query, given a node v and an integer value ≤ µ(v), asks for the highest ancestor u of v such that µ(u) ≥ , i.e., such an ancestor u that µ(u) ≥ and µ(u) is the smallest possible. When T is the suffix tree of a string x of length n, we can locate any factor x[i . . j] using a weighted ancestor query. We define the weight of a node of the suffix tree as the length of the string it represents. Thus a weighted ancestor query can be used for the terminal node corresponding to x[i . . n -1] to create (if necessary) and mark the node that corresponds to x[i . . j]. Given a collection Q of weighted ancestor queries on a weighted tree T on n nodes with integer weights up to n O (1) , all the queries in Q can be answered offline in O(n + |Q|) time [START_REF] Kociumaka | A linear time algorithm for seeds computation[END_REF].

Square-Free-Preserved Matching Statistics

In this section, we introduce the square-free-preserved matching statistics problem and provide a linear-time solution for it. In the square-free-preserved matching statistics problem we are given a string x of length n and we are asked to construct a data structure over x answering the following type of online queries: given a string y, find the longest square-free prefix of y[i . . |y| -1] that is a factor of x, for all 0 ≤ i < |y| -1. (For related work see [START_REF] Dumitran | On prefix/suffix-square free words[END_REF].) We represent the answer using an integer array SQMS y [0 . . |y| -1] of lengths, but we can trivially modify our algorithm to report the actual factors. It should be clear that a maximum element in SQMS gives the length of some longest square-free factor common to x and y.

Construction. Our data structure over a string x consists of the following:

• An integer array L x [0 . . n -1],
where L x [i] stores the length of the longest square-free factor starting at position i of string x.

• The suffix tree ST(x) of string x.

The idea for constructing array L x efficiently is based on the following crucial observation. Observation 1. If x[i . . n -1] contains a square then L x [i] + 1, for all 0 ≤ i < n, is the length of the shortest prefix of x[i . . n -1] (factor f ) containing a square. In fact, the square is a suffix of f , otherwise f would not have been the shortest. If x[i . . n -1] does not contain a square then L x [i] = n -i.

We thus shift our focus to computing the shortest such prefixes. We start by considering the runs of x. Specifically, we consider squares in x observing that a run [ , r] with period p contains r --2p + 2 squares of length 2p with the leftmost one starting at position . Let r = +2p-1 denote the ending position of the leftmost such square of the run. In order to find, for all i's, the shortest prefix of x[i . . n -1] containing a square s, and thus compute L x [i], we have two cases:

1. s is part of a run [ , r] in x that starts after i. In particular, s = x[ . . r ] such that r ≤ r, > i,
C[i] = S[i] = ∞ (x[i . . n -1] does not contain a square) we set L x [i] = n -i; otherwise (x[i . . n -1] contains a square) we set L x [i] = min{C[i], S[i]} -1.
Finally, we build the suffix tree ST(x) of a string x in O(n) time [START_REF] Farach | Optimal suffix tree construction with large alphabets[END_REF]. This completes our construction.

Querying. We rely on the following fact for answering the queries efficiently.

Fact 1. Every factor of a square-free string is square-free.

Let string y be an online query. Using ST(x), we compute the matching statistics MS y of y with respect to x. Recall that for each j ∈ [0, |y| -1], MS y [j] = ( j , p j ) indicates that the longest prefix of y[j . . |y| -1] that is a factor of x has length j and starts at position p j in x.

This computation can be done in O(|y|) time [START_REF] Gusfield | Algorithms on Strings, Trees, and Sequences -Computer Science and Computational Biology[END_REF][START_REF] Belazzougui | Indexed matching statistics and shortest unique substrings[END_REF]. By applying Fact 1, we can answer any query y in O(|y|) time for σ = O(1) by setting SQMS y [j] = min{ j , L x [j]}, for all 0 ≤ j ≤ |y| -1. We thus obtain the following result. Proof. The time complexity of our algorithm follows from the above discussion.

We next show the correctness of our algorithm. Let us first show the correctness of computing array L x . The square contained in the shortest prefix of x[i . . n -1] (containing a square) starts by definition either at i or after i. If it starts at i this is correctly computed by the algorithm of [START_REF] Duval | Lineartime computation of local periods[END_REF] which assigns the length of the shortest such square in S[i]. If it starts after i it must be the leftmost square of another run by the runs definition. C[i] stores the length of the shortest prefix containing such a square. Then by Observation 1, L x [i] is computed correctly.

It suffices to show that, if w is the longest square-free factor common to x and y occurring at position i x in x and at position i y in y, then (i)

MS y [i y ] = ( , i x ) with ≥ |w| and x[i x . . i x + -1] = y[i y . . i y + -1]; (ii) w is a prefix of x[i x . . i x + L x [i x ] - 1
]; and (iii) SQMS y [i y ] = |w|. Fact (i) directly follows from the correctness of the matching statistics algorithm. (ii) holds because, if w occurs at i x and w is square-free, then L x [i x ] ≥ |w|. Finally, for (iii), since w is square-free we have to show that |w| = min{ , L x [i]}. We know from (i) that ≥ |w| and from (ii) that L x [i x ] ≥ |w|. If min{ , L x [i]} = , then w cannot be extended because the possibly longer than |w| squarefree string occurring at i x does not occur in y, and in this case |w| = . Otherwise, if min{ i , L x [i]} = L x [i x ] then w cannot be extended because it is no longer square-free, and in this case |w| = L x [i x ]. Hence we conclude that SQMS y [i y ] = |w|. The statement follows.

The following example provides a complete overview of the workings of our algorithm.

C[i] 5 6 5 4 3 5 5 4 3 ∞ ∞ S[i] 2 4 4 6 ∞ 2 4 ∞ ∞ 2 ∞ L x [i] 1 3 3 3 2 1 3 3 2 1 1 j 0 1 2 3

Longest Periodic-Preserved Common Factor

In this section, we introduce the longest periodic-preserved common factor problem and provide a linear-time solution. In the longest periodic-preserved common factor problem, we are given k ≥ 2 strings x 0 , x 1 , . . . , x k-1 of total length N and an integer 1 < k ≤ k, and we are asked to find a longest periodic factor common to at least k strings. In what follows we present two different algorithms to solve this problem. We represent the answer LPCF k by the length of a longest factor, but we can trivially modify our algorithms to report an actual factor.

Our first algorithm, denoted by lPcf, works as follows.

1. Compute the runs of string x j , for all 0 ≤ j < k.

2. Construct the generalised suffix tree GST(x 0 , x 1 , . . . , x k-1 ) of the strings x 0 , x 1 , . . . , x k-1 . 3. For each string x j and for each run [ , r] with period p of x j , augment GST with the explicit node spelling x j [ . . r], annotate it with p , and mark it as a candidate node. This can be done as follows: for each run [ , r] of x j , for all 0 ≤ j < k, find the leaf corresponding to x j [ . .

|x j |-1]
and answer the weighted ancestor query in GST with weight r-+1. Moreover, mark as candidates all explicit nodes spelling a prefix of length d of any run [ , r] with 2p ≤ d. 4. Mark as good the nodes of the tree having at least k different colours on the leaves of the subtree rooted there. Let aGST be this augmented tree. 5. Return as LPCF k the string depth of a candidate node in aGST which is also a good node, and that has maximal string depth (if any, otherwise return 0). Proof. Let us assume wlog that k = k, and let w with period p be a longest periodic factor common to all strings. By the construction of aGST (Steps 1-4), the path spelling w leads to a good node n w as w occurs in all the strings. We make the following observation. Observation 2. Each periodic factor with period p of a string x is a factor of x[i . . j], where [i, j] is a run with period p. By Observation 2, in all strings, w is included in a run having the same period. Observe that for at least one of the strings, there is a run ending with w, otherwise we could extend w obtaining a longer periodic common factor (similarly, for at least one of the strings, there is a run starting with w). Therefore n w is both a good and a candidate node. By definition, n w is at string depth at least 2p and, by construction, LPCF k is the string depth of a deepest such node; thus |w| will be returned by Step 5. As for the time complexity, Step 1 [START_REF] Kolpakov | Finding maximal repetitions in a word in linear time[END_REF][START_REF] Bannai | The "runs" theorem[END_REF] and Step 2 [START_REF] Farach | Optimal suffix tree construction with large alphabets[END_REF] can be done in O(N ) time. Since the total number of runs is less than N [START_REF] Bannai | The "runs" theorem[END_REF], Step 3 can be done in O(N ) time using offline weighted ancestor queries [START_REF] Kociumaka | A linear time algorithm for seeds computation[END_REF] to mark the runs as candidate nodes; and then a post-order traversal to mark their ancestor explicit nodes as candidates, if their string-depth is at least 2p for any run [ , r] with period p . The size of the aGST is still in O(N ). Step 4 can be done in O(N ) time [START_REF] Hui | Color set size problem with applications to string matching[END_REF]. Step 5 can be done in O(N ) by a post-order traversal of aGST.

The following example provides a complete overview of the workings of our algorithm.

Example 3.2. Consider x =ababbabba, y =ababaab, and k = k = 2. The runs of x are: [START_REF] Kociumaka | Sublinear space algorithms for the longest common substring problem[END_REF][START_REF] Starikovskaya | Time-space trade-offs for the longest common substring problem[END_REF], per(bb) = 1, and r 3 = [6, 7], per(bb) = 1; those of y are r 4 = [0, 4], per(ababa) = 2 and r 5 = [START_REF] Starikovskaya | Time-space trade-offs for the longest common substring problem[END_REF][START_REF] Federico | Suffix tree characterization of maximal motifs in biological sequences[END_REF], per(aa) = 1. Figure 1 shows aGST for x, y, and k = k = 2. Algorithm lPcf outputs 4 = |abab|, with per(abab) = 2, as the node spelling abab is the deepest good one that is also a candidate.

r 0 = [0, 3], per(abab) = 2, r 1 = [1, 8], per(babbabba) = 3, r 2 =
The solution for offline weighted ancestor queries ( [START_REF] Kociumaka | A linear time algorithm for seeds computation[END_REF]) maintains a unionfind data structure which stores a partition of the nodes of the suffix tree. We next present a second algorithm to solve this problem with the same time complexity but without the use of offline weighted ancestor queries.

Our second algorithm works as follows.

1. Compute the runs of string x j , for all 0 ≤ j < k.

2. Construct the generalised suffix tree GST(x 0 , x 1 , . . . , x k-1 ) of the strings x 0 , x 1 , . . . , x k-1 . 3. Mark as good the nodes of GST having at least k different colours on the leaves of the subtree rooted there. 4. Compute and store, for every leaf node, the nearest ancestor that is good. 5. For each string x j and for each run [ , r] with period p of x j , check the nearest good ancestor for the leaf corresponding to Let us analyse this algorithm. Let us assume wlog that k = k, and let w with period p be a longest periodic factor common to all strings. By the construction of GST (Steps 1-3), the path spelling w leads to a good node n w as w occurs in all the strings. By Observation 2, in all strings, w is included in a run having the same period. Observe that for at least one of the strings, there is a run starting with w, otherwise we could extend w obtaining a longer periodic common factor. So the algorithm should check, for each run, if there is a periodic-preserved common prefix of the run and take the longest such prefix. LPCF k is the string depth of a deepest good node spelling a periodic factor; thus |w| will be returned by Step 6.

As for the time complexity, Step 1 [START_REF] Kolpakov | Finding maximal repetitions in a word in linear time[END_REF][START_REF] Bannai | The "runs" theorem[END_REF] and Step 2 [START_REF] Farach | Optimal suffix tree construction with large alphabets[END_REF] can be done in O(N ) time. Step 3 can be done in O(N ) time [START_REF] Hui | Color set size problem with applications to string matching[END_REF] and Step 4 can be done in O(N ) time by using a tree traversal. Since the total number of runs is less than N [START_REF] Bannai | The "runs" theorem[END_REF], Step 5 can be done in O(N ) time. We thus arrive at the result of Theorem 3.1 with a different algorithm.

The following example provides a complete overview of the workings of our algorithm.

Longest Palindromic Common Factor

In this section, we introduce the longest palindromic-preserved common factor problem and provide a linear-time solution. In the longest palindromicpreserved common factor problem, we are given two strings x and y, and we are asked to find a longest palindromic factor common to the two strings. For related work in a dynamic (resp. degenerate strings) setting see [START_REF] Funakoshi | Longest substring palindrome after edit[END_REF][START_REF] Amir | Longest Common Substring Made Fully Dynamic[END_REF] (resp. see [START_REF] Alzamel | Degenerate string comparison and applications[END_REF]). We represent the answer LPALCF by the length of a longest factor, but we can trivially modify our algorithm to report an actual factor. Our algorithm is denoted by lPalcf. In the description below, for clarity, we consider odd-length palindromes only. (Even-length palindromes can be handled in an analogous manner.) 1. Compute the maximal odd-length palindromes of x and the maximal odd-length palindromes of y. 2. Collect the factors x[i . . i ] of x (resp. the factors y[j . . j ] of y) such that i (resp. j) is the center of an odd-length maximal palindrome of x (resp. y) and i (resp. j ) is the ending position of the odd-length maximal palindrome centered at i (resp. j). 3. Create a lexicographically sorted list of such factors of x and y; compute the longest common prefix of consecutive entries (strings) in the list.

4. Let be the maximal length of longest common prefixes between any factor of x and any factor of y. For odd lengths, return LPALCF= 2 -1. Proof. The correctness of our algorithm follows directly from the following observation. Observation 3. Any longest palindromic-preserved common factor is a factor of a maximal palindrome of x with the same center and a factor of a maximal palindrome of y with the same center.

Step 1 can be done in O(|x|+|y|) time [START_REF] Gusfield | Algorithms on Strings, Trees, and Sequences -Computer Science and Computational Biology[END_REF].

Step 2 can be done in O(|x|+|y|) time by going through the set of maximal palindromes computed in Step 1.

Step 3 can be done in O(|x| + |y|) time by constructing the data structure of [START_REF] Charalampopoulos | Property suffix array with applications[END_REF]. Step 4 can be done in O(|x| + |y|) time by going through the list of computed longest common prefixes.

The following example provides a complete overview of the workings of our algorithm. We sort these strings lexicographically (Step 3), obtaining (we underline the maximal longest common prefixes for convenience) a, a, a, ab, ab, aba, b, b, b, ba, ba, bab, and compute the longest common prefix information. We find that = 2 with the maximal longest common prefixes being ba and ab, denoting that aba and bab are the longest palindromicpreserved common factors of odd length. Algorithm lPalcf outputs 2 -1 = 3 because aba and bab are the longest palindromic-preserved common factors.

Final Remarks

In this paper, we introduced a new family of string processing problems. The goal is to compute factors common to a set of strings preserving a specific property and having maximal length. We showed linear-time algorithms for square-free, periodic, and palindromic factors under three different settings.

We remark that our paradigm can be extended to other string properties or settings, as it was done in [START_REF] Kai | On longest common property preserved substring queries[END_REF] after the preliminary version of this work. We leave, for example, unbordered factors [START_REF] Kociumaka | Longest Unbordered Factor in Quasilinear Time[END_REF], quasiperiodic factors [START_REF] Christou | Efficient seed computation revisited[END_REF], or closed factors [START_REF] Fici | Open and closed words[END_REF] for future investigation.

Theorem 2 . 1 .

 21 Given a string x of length n over an alphabet of size σ = O(1), we can construct a data structure of size O(n) in time O(n), answering SQMS y online queries in O(|y|) time.

Example 2 . 2 .

 22 Let x = aababaababb and y = babababbaaab. The length of a longest common square-free factor is 3, and the factors are bab and aba.

  a b a b b a a a b MS y [j] (4,2)(5,1)(4,2)(5,6)(4,7)(3,8)(2,9)(3,4)(2,0)(3,0)(2,1)(1,2) SQMS y [j

Theorem 3 . 1 .

 31 Given k input strings of total length N on an alphabet Σ = {1, . . . , N O(1) }, and an integer 1 < k ≤ k, algorithm lPcf returns LPCF k in time O(N ).

Figure 1 :

 1 Figure 1: aGST for x = ababbabba, y =ababaab, and k = k = 2.

Figure 2 :

 2 Figure 2: GST for x = ababaa, y = bababb, and k = k = 2.

  x j [ . . |x j | -1]. Let d be the string-depth of the nearest good ancestor. Then: (a) If r -+ 1 ≤ d, the entire run is also good. (b) If r -+ 1 > d, check if 2p ≤ d, and if so the string for the good ancestor is periodic. 6. Return as LPCF k the maximal string depth found in Step 5 (if any, otherwise return 0).

Example 3 . 3 .

 33 Consider x =ababaa, y =bababb, and k = k = 2. The runs of x are: r 0 = [0, 4], per(ababa) = 2, r 1 = [4, 5], per(aa) = 1; those of y are r 2 = [0, 4], per(babab) = 2 and r 3 = [4, 5], per(bb) = 1. Figure 2 shows GST for x, y, and k = k = 2. Consider the run r 0 = [0, 4]. The nearest good node of leaf spelling x[0 . . |x| -1] is the node spelling abab. We have that r -+ 1 = 5 > d = 4, and 2p = 4 ≤ d = 4. The algorithm outputs 4 = |abab| as abab is a longest periodic-preserved common factor. Another longest periodic-preserved common factor is baba.

Theorem 4 . 1 .

 41 Given two strings x and y on alphabet Σ = {1, . . . , (|x| + |y|) O(1) }, algorithm lPalcf returns LPALCF in time O(|x| + |y|).

Example 4 . 2 .

 42 Consider x = ababaa and y = bababb. In Step 1 we compute all maximal palindromes of x and y. Considering odd-length palindromes gives the following factors at Step 2 from x: x[0 . . 0] = a, x[1 . . 2] = ba, x[2 . . 4] = aba, x[3 . . 4] = ba, x[4 . . 4] = a, and x[5 . . 5] = a. The analogous factors from y are: y[0 . . 0] = b, y[1 . . 2] = ab, y[2 . . 4] = bab, y[3 . . 4] = ab, y[4 . . 4] = b, and y[5 . . 5] = b.

  This implies that if i ≤ r-2p+1 then a square starts at i and we store the length of the shortest such square in an integer array S[0 . . n -1]. If no square starts at position i we set S[i] = ∞. Array S can be constructed in O(n) time by applying the algorithm of[START_REF] Duval | Lineartime computation of local periods[END_REF]. Since we do not know which of the two cases holds, we compute both C and S. By Observation 1, if

and r is minimal. In this case the shortest factor has length + 2p -i; we store this value in an integer array C[0 . . n -1]. If no run starts after position i we set C[i] = ∞. To compute C, after computing in O(n) time all the runs of x with their p and r

[START_REF] Kolpakov | Finding maximal repetitions in a word in linear time[END_REF][START_REF] Bannai | The "runs" theorem[END_REF]

, we sort them by r . A right-to-left scan after this sorting associates to i the closest r with > i. 2. s is part of a run [ , r] in x and i ∈ [ , r].

Acknowledgements

We would like to acknowledge an anonymous reviewer of a previous version of this paper who suggested the second linear-time algorithm for computing a longest periodic-preserved common factor.

Solon P. Pissis and Giovanna Rosone are partially supported by the Royal Society project IE 161274 ("Processing uncertain sequences: combinatorics and applications". Giovanna Rosone and Nadia Pisanti are partially supported by the project MIUR-SIR CMACBioSeq ("Combinatorial methods for analysis and compression of biological sequences") grant n. RBSI146R5L. Roberto Grossi is partially supported by MIUR Grant 20174LF3T8 AHeAD: efficient Algorithms for HArnessing networked Data.