# Quasi-Linear-Time Algorithm for Longest Common Circular Factor

Mai Alzamel, Maxime Crochemore, Costas S Iliopoulos, Tomasz Kociumaka, Jakub Radoszewski, Wojciech Rytter, Juliusz Straszyński, Tomasz Waleń, Wiktor Zuba

► To cite this version:

Mai Alzamel, Maxime Crochemore, Costas S Iliopoulos, Tomasz Kociumaka, Jakub Radoszewski, et al. Quasi-Linear-Time Algorithm for Longest Common Circular Factor. 30th Annual Symposium on Combinatorial Pattern Matching (CPM 2019), Nadia Pisanti and Solon P. Pissis, Jun 2019, Pisa, Italy. pp.25:1–25:14, 10.4230/LIPIcs.CPM.2019.25 . hal-04338883

HAL Id: hal-04338883

https://hal.science/hal-04338883v1

Submitted on 12 Dec 2023

**HAL** is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons CC0 1.0 - Universal - International License
# Quasi-Linear-Time Algorithm for Longest Common Circular Factor

## Mai Alzamel

Department of Informatics, King's College London, London, UK

mai.alzamel@kcl.ac.uk

https://orcid.org/0000-0002-7590-9919

## Maxime Crochemore

Department of Informatics, King's College London, London, UK

maxime.crochemore@kcl.ac.uk

## Costas S. Iliopoulos

Department of Informatics, King's College London, London, UK

costas.iliopoulos@kcl.ac.uk

https://orcid.org/0000-0003-3909-0077

## Tomasz Kociumaka

Institute of Informatics, University of Warsaw, Warsaw, Poland

kociumaka@mimuw.edu.pl

https://orcid.org/0000-0002-2477-1702

## Jakub Radoszewski

Institute of Informatics, University of Warsaw, Warsaw, Poland

jrad@mimuw.edu.pl

https://orcid.org/0000-0002-0067-6401

## Wojciech Rytter

Institute of Informatics, University of Warsaw, Warsaw, Poland

rytter@mimuw.edu.pl

https://orcid.org/0000-0002-9162-6724

## Juliusz Straszyński

Institute of Informatics, University of Warsaw, Warsaw, Poland

j.straszynski@mimuw.edu.pl

https://orcid.org/0000-0003-2207-0053

## Tomasz Waleń

Institute of Informatics, University of Warsaw, Warsaw, Poland

walen@mimuw.edu.pl

https://orcid.org/0000-0002-7369-3309

## Wiktor Zuba

Institute of Informatics, University of Warsaw, Warsaw, Poland

w.zuba@mimuw.edu.pl

## Abstract

We introduce the Longest Common Circular Factor (LCCF) problem in which, given strings *S* and *T* of length *n*, we are to compute the longest factor *UV* of string *S* whose cyclic shift *VU* occurs as a factor of string *T*. The LCCF is a new similarity measure that is an extension of the classic Longest Common Factor problem to circular pattern matching. We show that the LCCF problem can be solved in $\tilde{O}(n)$ time<fnref n="1" />. Our algorithm is randomized (Las Vegas). We apply

<footnote n="1">¹ The $\tilde{O}$ notation ignores factors polylogarithmic with respect to the instance size (encoded in binary).</footnote>
XX:2 Quasi-Linear-Time Algorithm for Longest Common Circular Factor

43

44

techniques of internal pattern matching (in case *U* and *V* are not highly periodic) and Lyndon
roots (otherwise) and reduce the problem to computing an intersection of 4D rectangles.

45

**2012 ACM Subject Classification** Theory of computation → Pattern matching

46

47

**Keywords and phrases** longest common factor, circular pattern matching, internal pattern matching, intersection of hyperrectangles

48

# 1 Introduction

49

50

51

52

53

We introduce a new variant of the Longest Common Factor (LCF) Problem, called the
Longest Common Circular Factor (LCCF) Problem. In the LCCF problem, given two strings
*S* and *T*, both of length *n*, we seek for the longest factor of *S* whose cyclic shift occurs as a
factor of *T*. The LCCF is a new string similarity measure that is 2-approximated by the
LCF. We show that the exact value of LCCF be computed efficiently.

54

55

56

57

58

59

60

61

A linear-time solution to the LCF problem is one of the best known applications of the suffix tree [2]. Just as the LCF problem was an extension of the classical pattern matching, the LCCF can be seen as an extension of the circular pattern matching problem. The latter can also be solved in linear time using the suffix tree and also admits a number of efficient solutions based on practical approaches [4, 9, 10, 11, 16, 20, 24, 27], also in the approximate variant [6, 7, 17, 19], as well as an indexing variants [3, 20, 21] and the problem of detecting various circular patterns [25]. The LCCF problem is also related to the notion of unbalanced translocations [8, 12, 26, 28, 29].

62

The problem in scope can be formally stated as follows.

LONGEST COMMON CIRCULAR FACTOR (LCCF)

63

Input: Two strings *S* and *T* of length *n* each

Output: A longest pair of factors, *F* of *S* and *F'* of *T*, for which there exist strings *U*
and *V* such that *F* = *UV* and *F'* = *VU*; we denote LCCF(*S*, *T*) = (*F*, *F*')

64

Our main result is the following.

**Main result.** The LCCF problem can be solved in $O(n \log^6 n)$ time by a randomized (Las Vegas) algorithm.

65

66

67

68

For simplicity, we will only consider computing the length of the LCCF. However, a
corresponding pair of factors can be retrieved in a straightforward way from the algorithm.

69

# 2 Preliminaries

70

71

72

73

74

75

76

77

We consider strings over an integer alphabet Σ. If *W* is a string, then by |*W*| we denote its length and by *W*[1],...,*W*[|*W*|] its characters. By *x* = *W*[*i*..*j*] we denote a *fragment* of *W* between the *i*th and *j*th character, inclusively. If *i* = 1, it is called a *prefix*, and if *j* = |*W*|, it is called a *suffix*. The string *W*[*i*]...*W*[*j*] that corresponds to the fragment *x* is called a *factor* of *W*. We say that two fragments *match* if their corresponding factors are the same. By *W*[*i*..*j*) we denote the fragment *W*[*i*..*j* − 1]. Fragments are further denoted by lowercase letters. Let us note that a factor of a given string that is specified by a fragment can be represented by its endpoints in O(1) space.

78

79

By $W^R$ we denote the reversal of the string $W$. By $\text{per}(W)$ we denote the shortest period of $W$. String $W$ is highly periodic iff $\text{per}(W) \le |W|/3$.
By the type of a fragment $u$ (type($u$)) we mean the largest $k$ such that $2^k \le |u|$. We denote by $\text{LCCF}_{a,b}(S,T) = (F, F')$ the longest common circular factor of $S, T$ such that $F = UV$, $F' = VU$, $U$ is of type $a$, and $V$ is of type $b$. We also say that it is the type-$(a, b)$ LCCF. Our strategy is to compute $\text{LCCF}_{a,b}(S,T) = (F, F')$ independently for each $a, b \le \log n$, and afterwards compute the longest alternative (over all pairs $(a, b)$) as the final result.

## 2.1 Synchronizing Functions

Let $W$ be a string of length $n$. By $\mathcal{F}_t(W)$ we denote the set of fragments of $W$ of length $t$ and by $\mathcal{N}_t(W)$ we denote the set of non-highly-periodic fragments of $W$ of length $t$. By $\mathcal{F}_t(x)$ and $\mathcal{N}_t(x)$ we denote subsets of these sets defined for a fragment $x$ of $W$.

A function sync: $\mathcal{F}_{2\tau-1}(W) \mapsto F_{\tau}(W) \cup \{\perp\}$ is called $\tau$-synchronizing if it satisfies the following conditions for each fragment $x \in \mathcal{F}_{2\tau-1}(W)$ (see [22]):

* If sync($x$) = $\perp$, then $\mathcal{N}_{\tau}(x) = \emptyset$;

* If sync($x$) $\neq \perp$, then sync($x$) $\in \mathcal{N}_{\tau}(x)$;

* If two fragments $x, x' \in \mathcal{F}_{2\tau-1}(W)$ are matching and sync($x$) = $x$[$s..s+\tau$) then sync($x'$) = $x'$[$s..s+\tau$) for the same $s$. In other words, if $x = W[p..q]$ and $x' = W[p'..q'$], then sync($x$) = $W[p+s..p+s+\tau]$ and sync($x'$) = $W[p'+s..p'+s+\tau)$.

The elements of $\mathcal{F}_{\tau}(W)$ for $\tau = 2^k$ are called here $\tau$-basic fragments.

**Example 1.** Let DBF($u$) be the identifier of a $\tau$-basic fragment $u$ of $W$ in the *Dictionary of Basic Factors*, see [14], and $\pi$ be a permutation of all (linearly many) $\tau$-basic identifiers. Each identifier is an integer in the range $[1..n]$. For a fragment $x$ of size $2\tau - 1$, we could define sync($x$) as the first $\tau$-basic fragment $u$ (from the left) with minimal DBF($u$). Then sync satisfies the conditions of the synchronizing function. If we take a random permutation $\pi$, then it has other useful properties in expectation, as shown in the lemma below.

The set of $\tau$-synchronizers for a fragment $x$, denoted by $\text{SYNC}_{\tau}(x)$, is $\text{sync}(\mathcal{F}_{2\tau-1}(W)) \cap \mathcal{N}_{\tau}(x)$. It follows from the construction of a $\tau$-synchronizing function of [22] and of [23].

**Lemma 2.** For all $\tau = 2^i$, $\tau \le n$, one can construct in $O(n \log n)$ total time a $\tau$-synchronizing function (stored in an array) such that for each fragment $x$ the expected number of $\tau$-synchronizers is $O(|x|/\tau)$.

*Proof.* Let $\mathcal{B}_{\tau}(S) = \{y \in \mathcal{N}_{\tau}(S) : \text{per}(y[1..\tau - 1]) \le \frac{\tau}{3} \text{ or } \text{per}(y[2..\tau]) \le \frac{\tau}{3}\}$. A set of integers $A$ is called $d$-sparse if $\min\{|a-b| : a, b \in A, a \neq b\} \ge d$. The following claim was presented as [22, Lemma 4.4.7].

**Claim 3.** $\mathcal{B}_{\tau}(S)$ is a union of two $\frac{\tau}{3}$-sparse sets.

For a step function $f$ on integers, by Steps($f$) we denote the number of positions such that $f(x) \neq f(x+1)$. The following fact shows the existence of a $\tau$-synchronizing function with a small number of steps and that it can be constructed efficiently. It was presented as Lemma 4.4.8 in [22]; it is also present in the non-periodic case of [23].

**Claim 4.** For a string $S$ of length $n$, there exists a $\tau$-synchronizing function sync such that $\text{Steps}(\text{sync}(\mathcal{F}_{2\tau-1}(S))) = O(n/\tau)$. Moreover, this function satisfies $\mathbb{P}[\text{sync}(x) = y] \le \frac{3}{\tau}$ for $y \in \mathcal{N}_{\tau}(x) \setminus \mathcal{B}_{\tau}(x)$ and it can be constructed (as an array) in $O(n)$ time.

We can now proceed to the proof of the lemma. The construction of a $\tau$-synchronizing function of Claim 4 can be applied. The fact that $|\text{SYNC}_{\tau}(x) \cap \mathcal{B}_{\tau}(S)| = O(|x|/\tau)$ in expectation follows from Claim 3 and the fact that $|\text{SYNC}_{\tau}(x) \cap (\mathcal{N}_{\tau} \setminus \mathcal{B}_{\tau}(S))| = O(|x|/\tau)$ in expectation follows from Claim 4. $\quad$
### 3 Nonperiodic-Nonperiodic Case

123

We say that a string $U$ of type $a$ is *a-highly periodic* if it has a period that is at most $2^{a-1}/3$. We consider now $\text{LCCF}_{a,b}(S, T) = (F, F')$ such that $F = UV, F' = VU, U$ is of type $a, V$ is of type $b, U$ is not *a-highly periodic*, and $V$ is not *b-highly periodic*. We call it *nonperiodic-nonperiodic* case.

124

125

126

127

We extend the function sync to all fragments by defining sync($u$) as the $2^{k-1}$-synchronizer of the prefix of $u$ of size $2^k$, where $k = \text{type}(u)$.

128

129

Let us define basic fragments called the left $k$-window and the right $k$-window:

130

$$ \text{LeftWin}_k(W, i) = W[i - 2^{k+1} \dots i - 1], \quad \text{RightWin}_k(W, i) = W[i \dots i + 2^{k+1} - 1] $$

131

132

For two triples $\Delta_1 = (x, i, y)$, $\Delta_2 = (y, i', x)$, where $x$ is a fragment both in $\text{LeftWin}(i, S)$ and in $\text{RightWin}_a(i', T)$ and $y$ is a fragment both in $\text{RightWin}(i, S)$ and in $\text{LeftWin}_b(i', T)$ define the pair $\text{CAND}(\Delta_1, \Delta_2) = (F, F')$ of fragments in $S$ and $T$ as follows, see Figure 1.

133

134

#### Relation of pairs of triples $(\Delta_1, \Delta_2)$ to LCCF$_{a,b}$

Let $j, k$ be starting positions of fragments $x, y$ in $S$.

Let $j', k'$ be starting positions of fragments $x, y$ in $T$.

$$ l := j' - i' + i - j, \quad r := k - i + i' - k' $$

135

Then $\text{CAND}(\Delta_1, \Delta_2) = (F, F')$, where

$$ F := S[i - l \dots i + r], \quad F' := T[i' - r \dots i' + l]. $$

$(F, F')$ is a candidate for $\text{LCCF}_{a,b}(S, T)$

Due to synchronization for any pair of $a, b$-triples $\Delta_1 = (x, i, y)$, $\Delta_2 = (y, i', x)$ there are exactly two fragments $U, V$ of types $a$ and $b$, such that $UV$ is "anchored" at $i$ in $S$ and $VU$ is "anchored" at $i'$ in $T$, $\text{sync}(U) = x, \text{sync}(V) = y$ and $[UV, VU]$ is a potential common circular factor. If $\text{CAND}(\Delta_1, \Delta_2) = (F, F')$, then $(F, F') = (UV, VU)$, $l = |U|, r = |V|$.

136

137

138

139

For a string $W$ we introduce the following sets of $2^{k-1}$-synchronizers:

140

$$ \text{LeftSynch}_k(W, i) = \text{SYNC}_{2^{k-1}}(\text{LeftWin}_{k+1}(W, i)) $$

141

$$ \text{RightSynch}_k(W, i) = \text{SYNC}_{2^{k-1}}(\text{RightWin}_{k+1}(W, i)) $$

142

Define $\text{Triples}_{c,d}(W) = \{(x, i, y) : x \in \text{LeftSynch}_c(W, i), y \in \text{RightSynch}_d(W, i), i \in [1..|W|]\}$.

143

144

Using the terminology of triples and function CAND (giving correspondence between pairs of triples and pairs of fragments), a scheme of a general algorithm can be written informally as follows:

145

146

147

#### Algorithm Compute-LCCF$_{a,b}$(S)

1. Compute the sets $\text{Triples}_{a,b}(S)$ and $\text{Triples}_{b,a}(T)$.

2. Find a pair of triples $\Delta_1 \in \text{Triples}_{a,b}(S)$, $\Delta_2 \in \text{Triples}_{b,a}(T)$ such that $\text{CAND}(\Delta_1, \Delta_2)$ corresponds to $\text{LCCF}_{a,b}(S, T)$.

148

► **Lemma 5.** In the nonperiodic-nonperiodic case the algorithm Compute-LCCF$_{a,b}$ correctly computes $\text{LCCF}_{a,b}(S, T)$.

149

150
However there are two difficulties in this approach that need to be overcome if the complexity should be $O(n)$.

Firstly, we cannot consider individually each combination, since the number of possible pairs $(i, i')$ is quadratic. We overcome this problem by a reduction to a geometric problem of the intersection of families of 4D rectangles.

Secondly, there is a difficulty of dealing with the case of highly periodic $U$ or $V$. We overcome it by using the machinery of *runs* and *Lyndon roots* of strings. In periodic case the role of synchronizers is played by fragments which are Lyndon roots.

## 4 4-Families-Problem

We reduce the second statement in the algorithm Compute-LCCF$_{a,b}$ to 4-FAMILIES-PROBLEM. A 4-tuple $(F_1, F_2, F_3, F_4)$ of strings agrees with a 4-tuple $(F'_1, F'_2, F'_3, F'_4)$ iff

$F'_1$ is a suffix of $F_1$, $F_2$ is a prefix of $F'_2$

$F_3$ is a suffix of $F'_3$, $F'_4$ is a prefix of $F_4$;

see Figure 1.

Our main auxiliary problem is defined as follows:

### 4-FAMILIES-PROBLEM

**Input:** A family $\mathcal{F}_S$ of 4-tuples $(F_1, F_2, F_3, F_4)$ of factors of $S$ and a family $\mathcal{F}_T$ of 4-tuples $(F'_1, F'_2, F'_3, F'_4)$ of factors of $T$, where $m = |\mathcal{F}_S| + |\mathcal{F}_T|$

**Output:** A 4-tuple $(F_1, F_2, F_3, F_4) \in \mathcal{F}_S$ which agrees with $(F'_1, F'_2, F'_3, F'_4) \in \mathcal{F}_T$ that maximizes $|F'_1| + |F'_2| + |F'_3| + |F'_4|$

<figure><img src="image_2.png" /><figcaption>Figure 1 (F_1, F_2, F_3, F_4) agrees with (F'_1, F'_2, F'_3, F'_4) iff CAND((x, i, y), (y, i', x)) corresponds to a common circular factor UV, where $U = F'_1 F_2$, $V = F_3 F'_4$.</figcaption></figure>

Denote $\text{Win}_{a,b}(W, i) = \text{LeftWin}_a(W, i) \text{RightWin}_b(W, i)$.

For each triple $(x, i, y) \in \text{Triples}_{a,b}(W)$ such that $x$ starts at position $j$ and $y$ starts at position $k$ we denote by $\Psi_{a,b}(x, i, y)$ the following factorization $(F_1, F_2, F_3, F_4)$ of $\text{Win}_{a,b}(W, i)$:

$$F_1 = S[i - 2^{a+1} + 1 \dots j), \quad F_2 = S[j \dots i), \quad F_3 = S[i \dots k), \quad F_4 = S[k \dots i + 2^{b+1}).$$

Moreover, by $\Psi'_{a,b}(x, i, y)$ we denote $(F_3, F_4, F_1, F_2)$.
► **Observation 6.** For two triples $\Delta_1 = (x, i, y)$, $\Delta_2 = (y, i', x)$ CAND($\Delta_1, \Delta_2$) is a common circular factor iff $\Psi(\Delta_1)$ agrees with $\Psi'(\Delta_2)$.

In the lemma below with high probability means, as usually, that the error probability is $O(n^{-c})$ for any specified constant $c > 0$.

► **Proposition 7.** After $O(n \log^2 n)$-time preprocessing, in the nonperiodic-nonperiodic case the LCCF$_{a,b}$ problem can be reduced to a 4-FAMILIES-PROBLEM($\mathcal{F}_S, \mathcal{F}_T$) in which $m = O(n \log n)$ with high probability.

**Proof.** If $(F_1, F_2, F_3, F_4) \in \mathcal{F}_1$ agrees with $(F'_1, F'_2, F'_3, F'_4) \in \mathcal{F}_2$, then $S$ and $T$ contain a common circular factor of length $|F'_1| + |F_2| + |F_3| + |F'_4|$; see Fig. 1. We will now show that if LCCF$_{a,b}$(S, T) = (F, F'), then the solution to 4-FAMILIES-PROBLEM($\mathcal{F}_1, \mathcal{F}_2$) is at least $|F|$.

Assume that $F = x_1x_2$ and $F' = y_2y_1$ where $x_1$ matches $y_1$, $x_2$ matches $y_2$, $2^a \le |x_1| \le 2^{a+1} - 1$, and $2^b \le |x_2| \le 2^{b+1} - 1$. Let $i$ be the starting position of fragment $x_2$ and $i'$ be the starting position of the fragment $y_1$. Let $\tau_1 = 2^{a-1}$, $\tau_2 = 2^{b-1}$, $x'_1$ and $y'_1$ be the prefixes of $x_1$ and $y_1$, respectively, of length $2\tau_1 - 1$, $x'_2$ and $y'_2$ be the prefixes of $x_2$ and $y_2$, respectively, of length $2\tau_2 - 1$, and:

$$x = \text{sync}_{\tau_1}(x'_1) = \text{sync}_{\tau_1}(y'_1), \quad y = \text{sync}_{\tau_2}(x'_2) = \text{sync}_{\tau_2}(y'_2).$$

Let $j$ and $k'$ be the starting positions of the synchronizing occurrences of $x$ in $x'_1$ and $y'_1$ and $k$ and $j'$ be the starting positions of the synchronizing occurrences of $y$ in $x'_2$ and $y'_2$. Then in the above construction, we will have $(F_1, F_2, F_3, F_4)$ in $\mathcal{F}_1$ where

$$F_1 = S[i - 2^{a+1} + 1..j), \quad F_2 = S[j..i), \quad F_3 = S[i..k), \quad F_4 = S[k..i + 2^{b+1}).$$

and $(F'_1, F'_2, F'_3, F'_4)$ in $\mathcal{F}_2$ where

$$F'_3 = T[i' - 2^{a+1} + 1..j'), \quad F'_4 = T[j'..i'), \quad F'_1 = T[i'..k'), \quad F'_2 = T[k'..i' + 2^{b+1}).$$

Moreover, $(F_1, F_2, F_3, F_4)$ agrees with $(F'_1, F'_2, F'_3, F'_4)$ due to the existence of $(F, F')$ and its weight $|F'_1| + |F_2| + |F_3| + |F'_4|$ equals $|F| = |F'|$.

The preprocessing of Lemma 2 takes $O(n \log^2 n)$ time. Afterwards, for given $a$ and $b$, the above construction produces, with high probability, two families $\mathcal{F}_1, \mathcal{F}_2$ with $|\mathcal{F}_1|, |\mathcal{F}_2| = O(n)$. ◀

## 5 Periodic-Periodic Case

We consider now LCCF$_{a,b}$(S, T) = (F, F') such that $F = UV$, $F' = VU$, $U$ is of type $a$, $V$ is of type $b$, $U$ is $a$-highly periodic, and $V$ is $b$-highly periodic.

For a string $W$, by HPerPref($U$) and HPerSuf($W$) we denote the maximal highly periodic prefix and suffix of $U$. Let us start with the following simple observation; see Fig. 2.

► **Observation 8.** Let $W$ and $W'$ be two strings for which the strings $X = HPerSuf(W)$ and $Y = HPerPref(W')$ have the same Lyndon root $\lambda$. Then the longest highly periodic suffix of $W$ that is also a prefix of $W'$ has length at least $\min(|X|, |Y|) - |\lambda|$.

Let us recall that Lyndon roots of runs can be computed in constant time after linear-time preprocessing [13] and that the 2-period query problem can be solved within the same complexities [23] (for a simplified solution of this problem, see [5]).

For a fragment $u$ denote by Lyndons($u$) the set of fragments in $u$ corresponding to the first/second/last occurrence of Lyndon root in the maximal highly periodic suffix of $u$ (if
<figure><img src="image_3.png" /><figcaption>Figure 2 Illustration of Observation 8.</figcaption></figure>

there is any such prefix/suffix) and by Lyndons'(u) the set of fragments in u corresponding to the first/penultimate/last occurrence of Lyndon root in the maximal highly periodic prefix of u (if there is any such prefix/suffix). We can redefine

$$ \text{Triples}_{a,b}(S) = \{ (x, i, y) : x \in \text{Lyndons}(\text{LeftWin}_a(i)), y \in \text{Lyndons}'(\text{RightWin}_b(i)) \}; $$

see Fig. 3.

<figure><img src="image_4.png" /><figcaption>Figure 3 Triples$_{a,b}$(S) for position i contains (x$_{p}$, i, y$_{q}$) for p, q ∈ {1, 2, 3}.</figcaption></figure>

**► Lemma 9.** The algorithm Compute-LCCF$_{a,b}$(S) for redefined triples correctly solves the periodic-periodic case.

195

196

$$ \text{Let us redefine: } \mathcal{F}_S = \{\Psi(x, i, y) \in \text{Triples}_{a,b}(S)\}, \mathcal{F}_T = \{\Psi'(x, i, y) \in \text{Triples}_{a,b}(T)\} $$

197

**► Proposition 10.** In the periodic-periodic case LCCF(S, T) corresponds to a solution of 4-FAMILIES-PROBLEM($\mathcal{F}_S$, $\mathcal{F}_T$) for $\mathcal{F}_S$, $\mathcal{F}_T$ defined above.

198

199

# 6 Nonperiodic-Periodic Case

200

Finally we consider the case that LCCF$_{a,b}$(S, T) = (F, F') such that F = UV, F' = VU, U is of type a, V is of type b, and either U is a-highly periodic or V is b-highly periodic. This case can be reduced to 4-FAMILIES-PROBLEM directly by combining the techniques of the previous two sections.

201

202

203

204

**► Proposition 11.** After $O(n \log^2 n)$-time preprocessing, in the nonperiodic-nonperiodic case the LCCF$_{a,b}$ problem can be reduced to a 4-FAMILIES-PROBLEM($\mathcal{F}_S$, $\mathcal{F}_T$) in which $m = O(n \log n)$ with high probability.

205

206

207
# 7 Solution to 4-Families-Problem

In this section we show how to solve the 4-FAMILIES-PROBLEM.

## 7.1 Intersecting 4D Rectangles

We define a *d*-rectangle ($d \ge 2$) as a Cartesian product of $d$ closed intervals, such that at least $d-2$ of them are singletons. E.g., $\{3\} \times [2, 5] \times [1, 7] \times \{0\}$ is a 4-rectangle. In other words, a *d*-rectangle is an isothetic hyperrectangle of dimension at most 2. Two *d*-rectangles $[a_1, b_1] \times \dots \times [a_d, b_d]$ and $[a'_1, b'_1] \times \dots \times [a'_d, b'_d]$ are called *compatible* if, for each $i \in \{1, \dots, d\}$, $[a_i, b_i]$ or $[a'_i, b'_i]$ is a singleton.

We consider two families of 4-rectangles with weights and wish to find a pair of intersecting rectangles, one per family, with maximum total weight. The general problem of finding such an intersection of two families of $m$ weighted hyperrectangles in $d$ dimensions can be solved in $\mathcal{O}(m \log^{2d} m)$ time by an adaptation of a classic approach [15]. Below we consider a special variant of the problem that has a much more efficient solution.

**MAX-WEIGHT INTERSECTION OF COMPATIBLE RECTANGLES IN 4D**

**Input:** Two families $R_1$ and $R_2$ of 4-rectangles in $\mathbb{Z}^4$ with integer weights containing $m$ rectangles in total, such that each $R_1 \in R_1$ and $R_2 \in R_2$ are compatible

**Output:** Check if there is an intersecting pair of 4-rectangles $R_1 \in R_1$ and $R_2 \in R_2$ and, if so, compute the maximum total weight of such a pair

A very similar problem was considered as Problem 3 in [18] for an arbitrary $d$. The sole difference is that the weight of an intersection of two $d$-rectangles $R_1 \in R_1$ and $R_2 \in R_2$ in that problem was the maximum $l_1$-norm of a point in $R_1 \cap R_2$. A solution to Problem 3 for $d=4$ in the case that the 4-rectangles are compatible working in $\mathcal{O}(m \log^3 m)$ time and $\mathcal{O}(m \log^2 m)$ space was given as [18, Lemma 5.8]. The algorithm presented in that lemma actually solves the MAX-WEIGHT INTERSECTION OF COMPATIBLE RECTANGLES IN 4D problem and applies it for specific weight assignment of the 4-rectangles on the input. It uses hyperplane sweep and a variant of an interval stabbing problem. Henceforth we will use the following result.

► Fact 12 ([18, see Lemma 5.8]). MAX-WEIGHT INTERSECTION OF COMPATIBLE RECTANGLES IN 4D can be solved in $\mathcal{O}(m \log^3 m)$ time and $\mathcal{O}(m \log^2 m)$ space.

## 7.2 Computations on Factor Intervals

The main tool in the solution are factor intervals. Before we describe them and how we operate on them, let us recall the basic properties of the suffix tree. Let us start with the following known fact.

► Fact 13 ([1]). Let $W$ be a string of length $n$ and $\mathcal{T}$ be its suffix tree. After $\mathcal{O}(n)$-time preprocessing, given a fragment $x$ of $W$, one can compute its locus in $\mathcal{T}$ in $\mathcal{O}(\log \log n)$ time.

Let $W$ be a string of length $n$. Let us consider the lexicographic order of factors of $W$. For two strings $X$ and $Y$ such that $X \le Y$, by $[X, Y]$ we denote the set of factors $F$ of $W$ such that $X \le F \le Y$. This set is referred to as a *factor interval*.

Similarly as for integers, one can define a *factor hyperrectangle* as a Cartesian product of factor intervals and a *factor *d*-rectangle* as a Cartesian product of *d* factor intervals such that at most two of them are not singletons. In our algorithm we will construct factor intervals
and factor 4-rectangles and use the following lemma to transform them into integer intervals
and 4-rectangles.

**Lemma 14.** Let $W$ be a string of length $n$ and $\mathcal{A}$ be a family of factor intervals whose endpoints are factors of $W$. In $O(n + |\mathcal{A}| \log \log n)$ time one can construct a function $f$ that maps factor intervals into integer intervals such that, for any $P, Q \in \mathcal{A}, P \cap Q \neq \emptyset$ iff $f(P) \cap f(Q) \neq \emptyset$. Moreover, if $P$ is a singleton, so is $f(P)$.

**Proof.** First we preprocess string $W$ to support lexicographically minimal factors of $W$ starting with given fragment $x$ using Lemma 16. This step takes $O(n)$ time.

For each factor $X$ of string $W$, we define function $g$ as $g(X) = (r, |X|)$ where $r$ is a rank of the lexicographically minimal suffix of $W$ starting with fragment of $X$. We can observe that for any factors $X, Y, X \le Y$ iff $g(X) \le g(Y)$.

Since we are interested only in values of function $g$ for endpoints of intervals from $\mathcal{A}$ we
can compute all such values of function $g$ in $|\mathcal{A}| \log \log n$ time, sort all those pairs in linear
time (using radix sort), and then define function $g'(X)$ as a rank of a pair in obtained sorted
sequences.

Finally for each interval $P = [X, Y]$, we define $f(P) = (g'(X), g'(Y))$.

Let # be a character that is greater than all the letters in Σ.

**Observation 15.** Assume that $P$ and $Q$ are factors of $W$. Then $P$ is a prefix of $Q$ iff $Q \in [P, P#]$ and a suffix of $Q$ iff $Q^R \in [P^R, P^R#]$.

As suggested in the above observation, in factor intervals we will also use, as right
endpoints, strings of the form $F#$ where $F$ is a factor of $W$. In order to transform them
into integer intervals with Lemma 14, we will compute the maximum factor of $W$ that starts
with $F$.

**Lemma 16.** Let $W$ be a string of length $n$. After $O(n)$-time preprocessing, given a fragment $x$ of $W$, one can compute the lexicographically minimal/maximal factor of $W$ that starts with a factor matching $x$ in $O(\log \log n)$ time.

**Proof.** First we compute in $O(n)$ time, the suffix tree of string $W$. Additionally we add to each explicit node the index of the lexicographically minimal/maximal suffix from its subtree. This can be easily done in $O(n)$ time by traversing the suffix tree. The last ingredient of our solution is preprocessing of the suffix tree for supporting weighted ancestor queries. Using solution from Fact 13 the preprocessing requires $O(n)$ time and each weighted ancestor query can be answered in $O(\log \log n)$ time.

Given fragment $x$ of $W$ starting at position $i$. We locate leaf $v$ of suffix tree corresponding
to the suffix $W[i..n]$. Using weighted ancestor query we locate the highest ancestor $u$ of
$v$, such that depth of $u$ is greater than (or equal to) $|x|$. The resulting lexicographically
minimal/maximal factor of $W$ (that starts with $x$) is the lexicographically minimal/maximal
suffix stored in the node $u$.

7.3 Algorithm for 4-Families-Problem

We are now ready to show a solution to 4-FAMILIES-PROBLEM.

**Lemma 17.** 4-FAMILIES-PROBLEM can be solved in $O(n + m \log^3 n)$ time and $O(m \log^2 n)$ space.
**Proof.** We construct two sets of factor 4-rectangles with weights, $\mathcal{R}_1$ and $\mathcal{R}_2$, from $\mathcal{F}_S$ and $\mathcal{F}_T$ over the concatenation $STS^RT^R$. For every $(F_1, F_2, F_3, F_4) \in \mathcal{F}_S$, we add a factor rectangle

$$ \{F_1^R\} \times [F_2, F_2\#] \times [F_3^R, F_3\#] \times \{F_4\} \text{ with weight } |F_2| + |F_3| $$

to $\mathcal{R}_1$. For every $(F'_1, F'_2, F'_3, F'_4) \in \mathcal{F}_T$, we add a factor rectangle

$$ [(F'_1)^R, (F'_1)^R\#] \times \{F'_2\} \times \{(F'_3)^R\} \times [F'_4, F'_4\#] \text{ with weight } |F'_1| + |F'_4| $$

to $\mathcal{R}_2$. By Observation 15, the solution of 4-FAMILIES-PROBLEM corresponds to two intersecting 4-rectangles $R_1 \in \mathcal{R}_1$ and $R_2 \in \mathcal{R}_2$ with maximum total weight.

Lemma 16 can be used to transform strings $X\#$ to factors of $STS^RT^R$. Then we apply Lemma 14 to transform factor 4-rectangles to standard 4-rectangles, dimension per dimension. Finally, we use Fact 12 to conclude.

As a consequence of Propositions 7, 10, and 11 applied for all a, b and the above lemma we obtain the main result.

**Theorem 18 (Main result).** The LCCF problem can be solved in $O(n \log^6 n)$ time by a randomized (Las Vegas) algorithm.

# 8 Conclusions

We have presented an $O(n \log^6 n)$-time randomized algorithm for computing the Longest Common Circular Factor (LCCF) of two strings of length $n$. Let us recall that the Longest Common Factor (LCF) of two strings can be computed in $O(n)$ time. We leave an open question if the LCCF problem can also be solved in linear time and if there exists a similarly efficient deterministic algorithm that solves this problem.

# References

1 Amihood Amir, Gad M. Landau, Moshe Lewenstein, and Dina Sokol. Dynamic text and static pattern matching. *ACM Trans. Algorithms*, 3(2):19, 2007. URL: https://doi.org/10.1145/1240233.1240242, doi:10.1145/1240233.1240242.

2 Alberto Apostolico, Maxime Crochemore, Martin Farach-Colton, Zvi Galil, and S. Muthukrishnan. 40 years of suffix trees. *Commun. ACM*, 59(4):66–73, 2016. URL: https://doi.org/10.1145/2810036, doi:10.1145/2810036.

3 Tanver Athar, Carl Barton, Widmer Bland, Jia Gao, Costas S. Iliopoulos, Chang Liu, and Solon P. Pissis. Fast circular dictionary-matching algorithm. *Mathematical Structures in Computer Science*, 27(2):143–156, 2017. URL: https://doi.org/10.1017/S0960129515000134, doi:10.1017/S0960129515000134.

4 Md. Aashikur Rahman Azim, Costas S. Iliopoulos, Mohammad Sohel Rahman, and M. Samiruzzaman. A fast and lightweight filter-based algorithm for circular pattern matching. In Pierre Baldi and Wei Wang, editors, *Proceedings of the 5th ACM Conference on Bioinformatics, Computational Biology, and Health Informatics, BCB '14, Newport Beach, California, USA, September 20-23, 2014*, pages 621–622. ACM, 2014. URL: https://doi.org/10.1145/2649387.2660804, doi:10.1145/2649387.2660804.

5 Hideo Bannai, Tomohiro I, Shunsuke Inenaga, Yuto Nakashima, Masayuki Takeda, and Kazuya Tsuruta. The "runs" theorem. *SIAM J. Comput.*, 46(5):1501–1514, 2017. URL: https://doi.org/10.1137/15M1011032, doi:10.1137/15M1011032.
321

322

323

6 Carl Barton, Costas S. Iliopoulos, and Solon P. Pissis. Fast algorithms for approximate circular string matching. *Algorithms for Molecular Biology*, 9:9, 2014. URL: https://doi.org/10.1186/1748-7188-9-9, doi:10.1186/1748-7188-9-9.

324

325

326

327

328

329

7 Carl Barton, Costas S. Iliopoulos, and Solon P. Pissis. Average-case optimal approximate circular string matching. In *Adrian-Horia Dediu, Enrico Formenti, Carlos Martín-Vide, and Bianca Truthe, editors, Language and Automata Theory and Applications - 9th International Conference, LATA 2015, Nice, France, March 2-6, 2015, Proceedings*, volume 8977 of *Lecture Notes in Computer Science*, pages 85-96. Springer, 2015. URL: https://doi.org/10.1007/978-3-319-15579-1_6, doi:10.1007/978-3-319-15579-1_6.

330

331

332

8 Domenico Cantone, Simone Faro, and Arianna Pavone. Sequence searching allowing for non-overlapping adjacent unbalanced translocations. *CoRR*, abs/1812.00421, 2018. URL: http://arxiv.org/abs/1812.00421, arXiv:1812.00421.

333

334

335

336

9 Kuei-Hao Chen, Guan-Shieng Huang, and Richard Chia-Tung Lee. Exact circular pattern matching using the bndm algorithm. In *Proceedings of the 28th Workshop on Combinatorial Mathematics and Computation Theory*, pages 152-161. National Penghu University of Science and Technology, Penghu, 2011.

337

338

339

340

10 Kuei-Hao Chen, Guan-Shieng Huang, and Richard Chia-Tung Lee. Exact circular pattern matching using bit-parallelism and q-gram technique. In *Proceedings of the 29th Workshop on Combinatorial Mathematics and Computation Theory*, pages 18-27. National Taipei College of Business, Institute of Information and Decision Sciences, Taipei, 2012.

341

342

343

11 Kuei-Hao Chen, Guan-Shieng Huang, and Richard Chia-Tung Lee. Bit-parallel algorithms for exact circular string matching. *Comput. J.*, 57:731-743, 2013. doi:10.1093/comjnl/bxt023.

344

345

346

12 Da-Jung Cho, Yo-Sub Han, and Hwee Kim. Alignment with non-overlapping inversions and translocations on two strings. *Theor. Comput. Sci.*, 575:90-101, 2015. URL: https://doi.org/10.1016/j.tcs.2014.10.036, doi:10.1016/j.tcs.2014.10.036.

347

348

349

350

13 Maxime Crochemore, Costas S. Iliopoulos, Marcin Kubica, Jakub Radoszewski, Wojciech Rytter, and Tomasz Walen. Extracting powers and periods in a word from its runs structure. *Theor. Comput. Sci.*, 521:29-41, 2014. URL: https://doi.org/10.1016/j.tcs.2013.11.018, doi:10.1016/j.tcs.2013.11.018.

351

352

14 Maxime Crochemore and Wojciech Rytter. *Jewels of Stringology*. World Scientific, 2003. doi:10.1142/4838.

353

354

15 Herbert Edelsbrunner. A new approach to rectangle intersections part i. *International Journal of Computer Mathematics*, 13:209-219, 1983. doi:10.1080/00207168308803364.

355

356

357

16 Kimmo Fredriksson and Szymon Grabowski. Average-optimal string matching. *J. Discrete Algorithms*, 7(4):579-594, 2009. URL: https://doi.org/10.1016/j.jda.2008.09.001, doi:10.1016/j.jda.2008.09.001.

358

359

360

17 Kimmo Fredriksson and Gonzalo Navarro. Average-optimal single and multiple approximate string matching. *ACM Journal of Experimental Algorithmics*, 9(1.4):1-47, 2004. URL: https://doi.org/10.1145/1005813.1041513, doi:10.1145/1005813.1041513.

361

362

363

18 Szymon Grabowski, Tomasz Kociumaka, and Jakub Radoszewski. On abelian longest common factor with and without RLE. *Fundam. Inform.*, 163(3):225-244, 2018. URL: https://doi.org/10.3233/FI-2018-1740, doi:10.3233/FI-2018-1740.

364

365

366

19 Tommi Hirvola and Jorma Tarhio. Bit-parallel approximate matching of circular strings with *k* mismatches. *ACM Journal of Experimental Algorithmics*, 22, 2017. URL: https://doi.org/10.1145/3129536, doi:10.1145/3129536.

367

368

369

370

20 Costas S. Iliopoulos, Solon P. Pissis, and M. Sohel Rahman. Searching and indexing circular patterns. In *Mourad Elloumi, editor, Algorithms for Next-Generation Sequencing Data, Techniques, Approaches, and Applications.*, pages 77-90. Springer, 2017. URL: https://doi.org/10.1007/978-3-319-59826-0_3, doi:10.1007/978-3-319-59826-0_3.
371

21 Costas S. Iliopoulos and M. Sohel Rahman. Indexing circular patterns. In Shin-Ichi Nakano and Md. Saidur Rahman, editors, WALCOM: Algorithms and Computation, Second International Workshop, WALCOM 2008, Dhaka, Bangladesh, February 7-8, 2008., volume 4921 of Lecture Notes in Computer Science, pages 46-57. Springer, 2008. URL: https://doi.org/10.1007/978-3-540-77891-2_5, doi:10.1007/978-3-540-77891-2\_5.

372

373

374

375

376

22 Tomasz Kociumaka. *Efficient Data Structures for Internal Queries in Texts*. PhD thesis, University of Warsaw, October 2018. URL: https://www.mimuw.edu.pl/~kociumaka/files/phd.pdf.

377

378

379

23 Tomasz Kociumaka, Jakub Radoszewski, Wojciech Rytter, and Tomasz Walen. Internal pattern matching queries in a text and applications. In Piotr Indyk, editor, *Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015*, San Diego, CA, USA, January 4-6, 2015, pages 532-551. SIAM, 2015. URL: https://doi.org/10.1137/1.9781611973730.36, doi:10.1137/1.9781611973730.36.

380

381

382

383

384

24 Jie Lin and Donald A. Adjerson. All-against-all circular pattern matching. *Comput. J.*, 55(7):897-906, 2012. URL: https://doi.org/10.1093/comjnl/bxr126, doi:10.1093/comjnl/bxr126.

385

386

387

25 Jie Lin, Yue Jiang, and Don Adjerson. Circular pattern discovery. *Comput. J.*, 58(5):1061-1073, 2015. URL: https://doi.org/10.1093/comjnl/bxu009, doi:10.1093/comjnl/bxu009.

388

389

390

26 H. Ogiwara, T. Kohno, H. Nakanishi, K. Nagayama, M. Sato, and J. Yokota. Unbalanced translocation, a major chromosome alteration causing loss of heterozygosity in human lung cancer. *Oncogene*, 27(35):4788-4797, 2008. doi:10.1038/onc.2008.113.

391

392

393

27 Robert Susik, Szymon Grabowski, and Sebastian Deorowicz. Fast and simple circular pattern matching. In Aleksandra Gruca, Tadeusz Czachórski, and Stanisław Kozielski, editors, *Man-Machine Interactions 3, Proceedings of the 3rd International Conference on Man-Machine Interactions, ICMMI 2013, Brenna, Poland, October 22-25, 2013*, volume 242 of *Advances in Intelligent Systems and Computing*, pages 537-544. Springer, 2013. URL: https://doi.org/10.1007/978-3-319-02309-0_59, doi:10.1007/978-3-319-02309-0\_59.

394

395

396

397

398

399

400

28 Dorothy Warburton. De novo balanced chromosome rearrangements and extra marker chromosomes identified at prenatal diagnosis: clinical significance and distribution of breakpoints. *Am. J. Hum. Genet.*, 49(5):995-1013, 1991. URL: https://www.ncbi.nlm.nih.gov/pubmed/1928105.

401

402

403

404

29 Brooke Weckselblatt, Karen E. Hermetz, and M. Katharine Rudd. Unbalanced translocations arise from diverse mutational mechanisms including chromothripsis. *Genome Res.*, 25(7):937-947, 2015. doi:10.1101/gr.191247.115.

405

406