The notion of circular string attractor has been recently introduced by Mantaci et al. [TCS 2021]. It consists of a set Γ of positions in a word such that each distinct circular factor has at least an occurrence crossing one of the elements of Γ. Its definition is an extension of the notion of string attractor by Kempa and Prezza [STOC 2018], which has been introduced as a unifying framework for some dictionary-based compressors. In this paper, we present the first linear time algorithm to check whether a set is a circular string attractor of a word ∈ {1, . . . , } by using ( log ) bits of space. We further show that, for each > 0, the decision problem of having a circular string attractor of size ≤ is NP-complete. The proof is obtained through a reduction from the analogous problem for string attractors, for which Kempa and Prezza [STOC 2018] proved the NP-completeness. This reduction naturally leads to a new algorithm for checking whether a set is a string attractor that, unlike one of the solutions proposed by Kempa et al. [ESA 2018], it is independent from the size of the alphabet.
show the properties that the data structures used verify, then we use these results to prove the
correctness of the algorithm proposed. Later, we analyze the complexity of the decision problem
of finding a circular string attractor of a word of size at most > 0. This complexity is
obtained through a reduction from analogous problem on classical string attractor, leading to a
new algorithm for checking whether a set Γ is a string attractor. Even if the bounds obtained are
analogous to those of one of the algorithms presented by [
An alphabet Σ is a set of elements called letters (or characters). We assume Σ to be finite, and we denote by = |Σ| its cardinality. A word (or string) is a sequence of letters from Σ, and its length is denoted by ||. We denote with the empty word, that is the only word such that || = 0. We denote by Σ* the set of all words over Σ, by Σ+ = Σ* ∖ {} the set of all non-empty words over Σ, and by Σ = { ∈ Σ* | || = } the set of all words of length , for some integer > 0. We denote by alph() ⊆ Σ the set of letters from Σ that occur in .
For each pair , ∈ [1, ], we denote by [, ] the factor (or substring) of starting at position and ending at position . Further, if = 1 or = , then [, ] is called prefix or sufix , respectively. Note that [1, ] = , and if > , we assume that [, ] = . The set of factors of a word is denoted by ℱ ().
Given two words , ∈ Σ* , if = [
If a total order on the elements of Σ is defined, then we can induce diferent orders on words. Given two words , ∈ Σ* , we say that ≤ if is prefix of , or there exists a word and two letters < ∈ Σ such that and are prefixes of and respectively. We refer to this order of the words as lexicographical order.
Given two words 1, 2 ∈ Σ* , we say that 1 is a conjugate (or cyclic rotation, or simply rotation) of 2 if there exist , ∈ Σ* such that 1 = and 2 = . We denote by ℛ() the set of rotations of the word . Note that ℛ(1) = ℛ(2) if and only if 1 and 2 are respectively conjugate. A finite word is then primitive if and only if |ℛ()| = ||, i.e., when all rotations of are distinct. A circular factor of a word is a factor that occur in at least one of the rotations of . The set of all circular factors of a word is denoted by () = ⋃︀′∈ℛ() ℱ (′).
The Sufix Array (SA) of a word ∈ Σ is an array of length such that [SA[], ] < [SA[], ] for every 1 ≤ < ≤ . The Inverse Sufix Array (ISA) is the inverse of SA, i.e. ISA[] = if and only if SA[] = . Analogously, let CA be the Conjugate Array of a word , defined as:
CA[] = if = [, ][1, − 1], where is the th rotation in lexicographical order.
Given two words , ∈ Σ* , let ℓ(, ) be the the longest common prefix between and ,
that is ℓ(, ) = [1, |ℓ(, )|] = [1, |ℓ(, )|], but [|ℓ(, )|+1] ̸= [|ℓ(, )|+1]
(assuming ℓ(, ) < min{||, ||}). The Longest Common Prefix Array (LCP) of ∈ Σ is an
array of length such that LCP[
LCP[] = ︂{ 0 |ℓ(− 1, )| if = 0 otherwise . [, ].
A string attractor of a word ∈ Σ is a set of positions Γ = {1, . . . , } such that every
factor [, ] has an occurrence [′, ′] = [, ] with ∈ [′, ′], for some ∈ [1, ] [
Throughout the paper, we will show examples of the algorithms applied on the family of
ifnite Fibonacci words , which can be defined recursively as follows: 0 = b, 1 = a, and
+1 = · − 1, for all integer > 1.
3. Circular String Attractors
Analogously to the definition of string attractor, Mantaci et al. [
Definition 1
Let ∈ Σ, for some > 0. A set Γ = {1, 2, . . . } ⊆ string attractor of if each circular factor of has at least a circular occurrence that crosses a position of Γ. Moreover, we denote with * () the size of a smallest circular string attractor of [1, ] is a circular the word .
Example 1 Let = be a word over the alphabet Σ = {, , }. The set Γ = {2, 5, 8} is a string attractor for , since it covers any of its factors, but it is not a circular string attractor since the circular factor (in blue) escapes from it. On the other hand, the set Γ = {1, 4, 9} is a circular string attractor for = but it is not a string attractor. In fact, the factor (in blue), fully contained in , is covered only if we consider its circular occurrence crossing position 1.
From the definition, it easily follows that the sizes * of smallest circular string attractors of
conjugate words are equal [
The following lemma shows not only that * () = * (), for all ∈ Σ* and integer Γ′ = ⋃︀
∈[1, ]{ + ||} is a circular string attractor of .
Lemma 1 Let ∈ Σ* be a finite word and
Γ = {1, 2, . . . , } ⊆ circular string attractor of if and only if, for all > 1 and for all ∈ [0, − [1, ||]. Then, Γ is a 1] , the set Proof For the first direction, note that since the word has period ||, all circular factors of length at most || which cross the position for some ∈ [1, ] have another occurrence crossing the position + ||. For all the circular factors of of length greater than ||, for the same argument we can find (at least) circular occurrences through at distance ||, covering the a a a a a a a a b b b b b a a a b b b b b a a a a a b b b a a a a a a a a b b a a a a a a b b b b b a a a b b b b b a a a a a a a b a a a a a a a a b b b b a a a a b b b b b a a a a b b b b a a a a a a a a b a a a a a a a b b b b b a b b b b b a a a a a a a a whole word, and therefore these factors can be moved to every other occurrence of where a position from Γ′ falls.
For the second implication, by hypothesis the set Γ is a circular string attractor of .
Symmetrically to the previous direction, since the set of all circular factors of of length at most ||
corresponds to the set (), and each of these circular factors from () is fully covered from the
elements in Γ, the thesis follows.
4. Checking the Circular Attractor Property in Linear Time
Given a word of length > 0, let us consider the matrix ℳ() = {1, . . . , } of the
rotations of sorted in lexicographical order. For every factor ∈ (), we denote with ℐ
the set of rotations from ℳ() starting with , taken in lexicographical order. In order to
give a high-level view of how the algorithm works, let us consider the finite Fibonacci word
6 = abaababaabaab. In Figure 1, it is shown the matrix of sorted rotations of 6 and, for each
rotation, the positions of a circular string attractor described in [
For each ∈ () ∖ {}, let ℓ, , with 1 ≤ ℓ ≤ ≤ , be the indices such that ℐ = {ℓ , ℓ+1, . . . , }. The following lemma summarises how to detect the indices ℓ and from the LCP array.
Lemma 2 Let ∈ Σ, for some > 0. The following hold: 1. ℓ = 1 or LCP[ℓ] < ||; 2. = or LCP[ + 1] < ||; 3. LCP[] ≥ | |, for all ∈ [ℓ + 1, ].
Proof For case 1., suppose ℓ > 1. By contradiction, if LCP[ℓ] ≥ , then also the rotation ℓ+1 has as prefix, which is a contradiction by hypothesis on ℓ.
Case 2. is treated symmetrically.
Case 3. follows by observing that all the rotations in ℐ are consecutive and share the same prefix of length ||. □
Given an ordered set Γ = {1, 2, . . . , } and a word ∈ Σ, let succ ∈ {0, 1, . . . , − 1} be the array of circular distances of each position ∈ [1, ] of to the next position in Γ, that is: succ[] = ⎧⎨ 1 − if 1 ≤ ≤ 1
+1 − if < ≤ +1, for all ∈ [1, − 1] ⎩ ( − ) + 1 if < .
Example 2 Let us consider the word = abbabaa and the set Γ = {3, 5, 6} (the underlined
positions in ). Then, succ = [
By Lemma 1, we know that a set Γ is a circular string attractor for the word , where > 1, if and only if Γ′ = ⋃︀∈Γ {( − 1 mod ||) + 1} is a circular string attractor of . Thus, we can assume that is primitive, otherwise we can find its root in linear time and check whether the set Γ′ obtained as just described is a circular string attractor of . Lemma 3 Let ∈ Σ be a primitive word, and let Γ ⊆ [1, ] be a set of positions in , for some > 0. Then, Γ is a circular string attractor of if and only if, for all ∈ (), there exists ∈ [ℓ, ] such that succ[CA[]] < ||.
Proof For the first implication, if Γ is a circular string attractor, then for each ∈ () there exists at least one occurrence that is crossed by a position ∈ Γ. Let ∈ [ℓ, ] be the index of the rotation starting with such an occurrence of . Thus, if we project the position from Γ in the th rotation, such a position falls at most at distance ||, and therefore succ[CA[]] is at most || − 1.
The other direction is treated symmetrically. In fact, by contradiction, if for all ∈ [ℓ, ] it holds that succ[CA[]] ≥ | |, then none of the occurrences of crosses a position in Γ, and therefore it can not be a circular string attractor; contradiction. □
Thus, in order to check whether a set Γ is a circular string attractor, we need to check if, for all ∈ (), there exists ∈ [ℓ, ] such that succ[CA[]] < ||. In Algorithm 1 we describe the designed procedure. We store in a stack the ranges of lengths of the circular factors left to cover, and proceeding by comparing in order the LCP with the succ array. We use Lemma 2 to understand if we are still in the range [ℓ, ] without even knowing , but just by using the LCP array (line 8). Note that this is legit since for all , ∈ Σ* it holds that [ℓ, ] ⊆ [ℓ, ], i.e., we can not leave the range [ℓ, ] before checking if the factor is covered within [ℓ, ]. The consecutive lengths of the circular factors left to cover are inserted as a pair (, ) in .
We can then obtain the following: Algorithm 1: Algorithm for checking if a set Γ is a circular string attractor of a word else if LCP[] ≤ succ[CA[]] then if = LCP[] then
.ℎ((, succ[CA[]])) else .ℎ((, )) if LCP[] 1<7 succ[CA[]] then .ℎ((LCP[] + 1, succ[CA[]])) 25 if is empty then 26 return true 27 else 28 return false else while is not empty ∧ succ[CA[]] ≤ do
(, ) ← .() if < succ[CA[]] then
.ℎ((, min{, succ[CA[]]})) else
if LCP[] < succ[CA[]] then .ℎ((LCP[] + 1, succ[CA[]])) Theorem 1 Given a primitive word ∈ Σ and a set Γ ⊆ [1, ], Algorithm 1 checks whether or not the set Γ is a circular string attractor for . Moreover, it runs in () time using ( log ) bits of space.
Proof The Conjugate Array CA can be computed in linear time [
The stack is initially empty, so at the iteration = 1 we start to fill it with the lengths of the
prefixes of the first rotation in lexicographical order that need to cross a position from Γ. Since
succ[CA[
On the iteration = 2, we pop from the stack the ranges of lengths (1, 4), and we compare the
maximum (4) with LCP[
Then, at the iteration = 3 (Subfigure 2c), the prefix a still occurs (LCP[
The algorithm proceeds as shown in Subfigure 2d, by shrinking the range (1, 6) to (1, 3) (line 22).
At the following iteration shown in Subfigure 2e the stack is emptied for the first time, since
succ[CA[
We keep following the procedure for the iterations 6, 7, and 8, respectively shown in Subfigures 2f, 2g, and 2h. Since at the end of the main loop the stack is empty, each circular factor crosses at least a position from Γ, and therefore we return true.
Remark 1 Given a pair (, ) in , every pair (′, ′) that goes on top of (, ) must verify that
′ > , since if ′ = then (, ) is replaced with (, ′). Thus, in the worst-case scenario would
contain the pairs (1, 1), (3, 3), . . . , (⌊︀ 2 ⌉︀ , ︀⌊ 2 ⌉︀ ), that is requires at most log bits of space.
Overall, Algorithm 1 requires up to 4 log bits of space to run.
5. Complexity of circular-attractor
In their original work, Kempa and Prezza [
In the same work, they proved that this problem is NP-complete. Here we define the analogous problem extended to the notion of circular string attractor:
circular-attractor = {⟨, ⟩ : has a circular string attractor of size ≤ }.
The following lemma shows a reduction to the analogous problem on circular string attractors. Lemma 4 Given an integer > 0, let ∈ Σ be a finite word and let $ ∈/ Σ. A set Γ is a string attractor for if and only if Γ ∪ { + 1} is a circular string attractor for $
CA
Proof Let $($) denote the set of all circular factors of $ containing the letter $. One can observe that ($) = ℱ () ∪ $($). Indeed, ℱ () ∩ $($) = ∅, and the position { + 1} is crossed by all and only circular factors from $($). Thus, the factors to cover in are the same as the circular factors in ($) ∖ $($), and since they are located in the same positions in both words the thesis follows. □
From the reduction above, we can deduce the computational complexity of the circular-attractor problem.
Theorem 2 The circular-attractor problem is NP-complete.
Proof By Theorem 1, each solution for the circular-attractor problem can be checked in polynomial
time and space, and therefore circular-attractor ∈ NP. Furthermore, Lemma 4 shows how to reduce
an instance ⟨, ⟩ for the problem attractor to circular-attractor by replacing and with $
and + 1 respectively, since for each string attractor Γ of the set Γ ∪ { + 1} is a circular string
attractor of $. □
6. Novel Algorithm for Checking the Attractor Property
If we consider the same problem on classical string attractors, Kempa et al. presented two
algorithms for checking whether a set Γ is a string attractor for a word ∈ Σ [
Here we present a novel algorithm taking the same time and space complexities as Algorithm 1. The algorithm is constructed from the strategies developed in Algorithm 1 and from the equivalence of Lemma 4. Recall that appending a $ smaller than any other symbol in Σ implies that CA = SA and LCP = LCP. We can then derive the following Theorem. Theorem 3 Given a word ∈ Σ and a set Γ ⊆ [1, ], Algorithm 2 checks whether or not the set Γ is a string attractor for in () time using ( log ) bits of space.
Proof The correctness of Algorithm 2 is derived from its equivalence in Lemma 4 with Algorithm 1. The Sufix Array SA, the LCP array, and the succ array can be computed in () time using ( log ) bits of space. Note that, unlike Algorithm 1, Algorithm 2 takes in input also words that are not primitive, since by appending the letter $ ∈/ Σ every word becomes primitive. Since Algorithm 2 takes the same time and space as Algorithm 1, the thesis follows. □ Example 4 Let us consider the word ′ = ababaaba, that is a rotation of the word 5 from Example 3, and let us consider the set of positions Γ = {7, 8}. In Figure 3, the iterations of Algorithm 2 with ′ and Γ in input are shown. Recall that we compute the LCP, succ, and SA arrays for the word ′$, and we extend Γ with the position of the $, i.e. Γ = {7, 8, 9}. 25 if is empty then 26 return true 27 else 28 return false else while is not empty ∧succ[SA[]] ≤ do
(, ) ← .() if < succ[SA[]] then
.ℎ((, min{, succ[SA[]]})) if LCP[] < succ[SA[]] then .ℎ((LCP[] + 1, succ[SA[]])) Algorithm 2: Algorithm for checking if a set Γ is a string attractor for a word
As shown in Subfigure 3a, at first the stack is empty and the condition of line 24 is not met, since
LCP[
Since at the third iteration the stack is still empty, each factor that is prefix of the first two rotations
has an occurrence crossing at least a position in Γ. Since this time 1 = LCP[
LCP = 0 0 1 1 3 3 0 2 2
SA → 9 8 5 6 3 1 7 4 2 SA 9 8 → 5 6 3 1 7 4 2 $ a b a b a a b a a $ a b a b a a b a a b a $ a b a b a b a $ a b a b a a b a a b a $ a b a b a b a a b a $ b a $ a b a b a a b a a b a $ a b a b a b a a b a $ a
(a) = 1 $ a b a b a a b a a $ a b a b a a b a a b a $ a b a b a b a $ a b a b a a b a a b a $ a b a b a b a a b a $ b a $ a b a b a a b a a b a $ a b a b a b a a b a $ a (c) = 3 ↓ (2, 2)
Finally, in Subfigure 3d, one can see that the factor aa does not occur as prefix in the following
rotations. In fact, at the iteration = 4 Algorithm 2 checks in line 9 whether the factor that we are
looking for occurs again as prefix by comparing LCP[
In this work, we have shown an easy reduction from the attractor decision problem to its circular version, leading to an NP-completeness for circular-attractor. We have also presented the first algorithm in literature that checks whether a set Γ is a circular string attractor for a word ∈ Σ, operating in () time and ( log ) bits of space. Furthermore, given the reduction above mentioned and the equivalence between the order of the rotations and order of the sufixes for words of the type $, we have presented a new algorithm for checking the attractor property of a set by using the sufix and the Longest Common Prefix Arrays, using the same time and space bound as the previous one. With respect to the solutions proposed by Kempa et al., the algorithm here proposed is independent from the size of the alphabet.