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

ifip

International Federation for Information Processing

This document is the original author manuscript of a paper submitted to an IFIP
conference proceedings or other IFIP publication by Springer Nature. As such, there
may be some differences in the official published version of the paper. Such
differences, if any, are usually due to reformatting during preparation for publication or
minor corrections made by the author(s) during final proofreading of the publication
manuscript.
Local Maximal Equality-Free Periodicities

Mai Alzamel¹, Jacqueline W. Daykin²,³,⁴, Christopher Hampson⁵, Costas S. Iliopoulos⁵, Zara Lim⁵(✉), and W. F. Smyth⁶

¹ Computer Science Department, King Saud University, Riyadh, Saudi Arabia
malzamel@ksu.edu.sa

² LITIS, Normandie University, 76000 Rouen, France

³ Department of Information Science, Stellenbosch University, Stellenbosch, South Africa

⁴ Department of Computer Science, Aberystwyth University, Wales, UK
jwd6@aber.ac.uk

⁵ Department of Informatics, King's College, London, UK
{christopher.hampson, csi, zara.lim}@kcl.ac.uk

⁶ Department of Computing and Software, McMaster University, Hamilton, ON, Canada
smyth@mcmaster.ca

**Abstract.** In this paper, we study local maximal antiperiodicities. Given a string $X$ and an integer $k$, we compute the maximal $k$-antiperiodicity starting at every position of $X$; that is, we identify a maximum-length sequence of distinct factors, where each is of length $k$. The space and time complexity of the algorithm is linear.

**Keywords:** Antiperiod · Equality-free · Antipower

# 1 Introduction

Antipowers, antiperiods and the generalised notion of “equality-free” strings can be traced back to applications in genomics and synthetic biology, where DNA strands are artificially constructed to produce novel or disease-resistant proteins [9]. In the construction of such synthetic strands, short strands of DNA (also known as oligo fragments) are produced by DNA synthesis machines; to synthesize longer DNA duplexes, many of these short DNA oligo fragments are assembled together [16]. The assembly of longer DNA sequences has strict regulations, including (i) the length of each strand must be bounded by a given value and (ii) two oligos must not collide (i.e. be too similar) in order to prevent them from hybridising with each other — otherwise it can inhibit proper assembly (see Condon et al. [7, 8] for more details). Thus the challenge is to identify which oligos are most suited for self-assembly. It follows that computing the equality-free factors of a string is a generalisation of this problem which can be extended to antipowers and antiperiods, whereby reporting equality-free factors of a string (similarly antiperiodic substrings) would ensure pairs of oligos are not so similar
as to prevent them from hybridising together. Furthermore, adding a bound on
the length of equality-free factors reciprocates the requirement for short oligos.

Condon et al. [7,8] investigated the problem of deciding whether a given
string W has an equality-free factorisation of width at most m, where the width
is the maximum length of any factor. This problem is also mentioned by Bulteau
et al. [5]; furthermore, Bannai et al. [4] investigate the hardness of computing
an equality-free factorisation with only palindromes as factors.

Antipowers and antiperiods are more recent variants of powers and periods.
Given a string $U$ of length $p \ge 1$, then for any integer $k \ge 1$, the string $X = U^k$
is a power of $U$ of order $k$ with period $p$. Then $X = U_1U_2...U_k$ is an antipower
of order $k$ and antiperiod $p$ if and only if $|U_i| = p, 1 \le i \le k$, and the $U_i$ are
pairwise distinct [12]. $X$ is also said to be $k$-antiperiodic [1].

The notion of powers can be traced back to the early 1900s by Thue who
presented results on strings which do not contain any substrings that are pow-
ers [17]. In 2018 Fici et al. [12] coined the term of antipowers, and showed that
every infinite string contains either powers or antipowers of any order. Antipow-
ers have been addressed by both combinatorial and algorithmic communities.

Defant [10] showed that the length of the shortest prefix of the Thue-Morse
string which are antipowers grows linearly in $k$. Gaetz [13] later extended this
result to substrings. Burcroff [6] generalised Fici et al.'s results to the avoidability
of $k$ antipowers in infinite strings. Badkobeh et al. [3] and Kociumaka et al. [15]
have presented algorithmic results, given a string $X$ of length $n$ and a parameter
$k$, all substrings of $X$ that are antipowers of order $k$ can be located in $O(n^2/k)$
time and $O(nk \log k + C)$, time respectively, where $C$ is the number of reported
fragments.

Alamro et al. [1] originated the definition of an antiperiod, and gave complex-
ity bounds for the offline computation of the minimum antiperiod and all the
antiperiods of a word. Their result is based on a weighted level ancestor prob-
lem, which has a similar result shown by Kociumaka et al. [14]. Later, Alzamel
et al. [2] address the same problems in the online setting.

In this paper, we discuss the *local maximal k-antiperiodicity problem*, which
given an input string $X$ and integer $k$ returns each of the maximal substrings of
$X$ which are $k$-antiperiodic with respect to each of the first $n-k+1$ indexes of
$X$. Note that the length of each $k$-antiperiodic substring must be a multiple of
$k$, and the last $k$ indices of a string are trivially a local maximal $k$-antiperiodic
 substring.

For example, given the string $X = aacbaabc$, and $k = 2$, the local maximal
2-antiperiodic substrings of $X$ are: $X[0..3]$, $X[1..6]$, $X[2..7]$, $X[3..6]$, $X[4..7]$,
$X[5..6]$, $X[6..7]$. Of these, the substrings $X[1..6]$ and $X[2..7]$ are the global
maximal 2-antiperiodic strings of $X$ (see Fig. 1).

We show that given a string $X$ and an integer $k$, all of the local maximal
$k$-antiperiodic substrings can be found in $O(n)$ time. The rest of the paper is
organised as follows: In Sect. 2, we discuss the preliminaries and definitions.
In Sect. 3, we present an overview of our algorithm. In Sect. 4, we discuss the
details of our algorithm. In Sect. 5 we perform an analysis on the algorithm, and
in Sect. 6 we present our conclusions.
<figure><img src="image_2.png" /><figcaption>**Fig. 1.** Given the string $X = aacbaabc$, and $k = 2$, the local maximal 2-antiperiodic substrings of $X$ are: $X[0..3]$, $X[1..6]$, $X[2..7]$, $X[3..6]$, $X[4..7]$, $X[5..6]$, $X[6..7]$. Of these, the substrings $X[1..6]$ and $X[2..7]$ are the global maximal 2-antiperiodic strings of $X$. If the substring $X[2..7]$ was extended $k(= 2)$ indices to the left, the string is no longer antiperiodic, hence the substring $X[2..7]$ is maximal.</figcaption></figure>

## 2 Preliminaries

A string is a sequence of zero or more symbols from an alphabet $\Sigma$. The set of all strings over the alphabet $\Sigma$ is denoted by $\Sigma^*$. We denote a string $X$ of length $n$ by $X[0..n-1] = X[0]..X[n-1]$, where $X[i] \in \Sigma$ for $0 \le i \le n-1$. We denote the length of string $X$ by $|X|$. A string $W$ is a substring or factor of $X$ if $X = UWV$ for $U, V \in \Sigma^*$; we equivalently say that the string $W$ occurs at position $|U| + 1$ of the string $X$. A string $W$ is a prefix of $X$ if $X = WU$ for $U \in \Sigma^*$. Similarly, $W$ is a suffix of $X$ if $X = UW$ for $U \in \Sigma^*$.

The string $XY$ is a concatenation of two strings $X$ and $Y$. The concatenations of $k$ copies of $X$ is denoted by $X^k$. For two strings $X = X[0..n-1]$ and $Y = Y[0..m-1]$ such that $X[n - i..n-1] = Y[i..m-1]$ for some $i \ge 1$, the string $X[0..n-1]Y[i..m]$ is a superposition of $X$ and $Y$. Let $X$ be a string of length $n$. We say that a prefix $X[0..p]$, $0 \le p < n-1$, of $X$ is a period of $X$ if $X[i] = X[i+p]$ for all $1 \le i \le n-p$.

An antipower of order $k$ (or $k$-antipower) is a string obtained by the concatenation of $k$ pairwise-distinct strings of identical length. The antiperiod of a $k$-antipower of length $n$ is $n/k$. For $0 \le i \le j \le n-1$, we say that $X[i..j]$ is a maximal $k$-antiperiodic substring of $X[0..n-1]$ if no longer $k$-antiperiodic string can be obtained by extending $X[i..j]$ to the left or right. Given a string $X$ of length $n$, for each index $i \in [0, n-1]$, we say that the local maximal $k$-antiperiodic substring of $X[i]$ is the maximal $k$-antiperiodic substring of $X$ beginning at position $i$. A global maximal $k$-antiperiodic substring of $X$ is a longest $k$-antiperiodic substring of $X$ — there may be more than one.

In our algorithm, we make use of the suffix tree data structure. The suffix tree provides a compact representation of the set of suffixes of the string $X$, in which each leaf node of the tree uniquely corresponds to one of the $n$ suffixes of $X$, which is determined by following the unique path from the root to the leaf and concatenating the edge labels as they are encountered. To ensure every suffix corresponds uniquely to a leaf node, the string $X$ may be extended by a unique `$` character not appearing elsewhere in $X$. An example suffix tree is shown in Fig. 2.
<figure><img src="image_3.png" /><figcaption>Fig. 2. Suffix tree for the string $X = AAABBAABBBBAABAAABBA$.</figcaption></figure>

## 3 An Outline of the Algorithm

Given a string $X$ of length $n$, each of the $n-(k-1)$ local maximal $k$-antiperiodic substrings can be computed in linear time as follows:

1. Construct the (unordered) suffix tree of $X$ in linear time.

2. Name each $k$-prefix of every suffix with a unique name.

3. Two equal $k$-prefixes take the same name, that is to say, all children of a $k$-prefix get the same name.

4. Store the name of the $k$-prefix of $X[i]$ in array $A_{(i \mod k)}$.

5. Scan $A_i$ from left-to-right and each name finds the first location of the same name to the right.

6. Identify each local maximal $k$-antiperiod starting from the rightmost position of each array.

7. The local maximal $k$-antiperiod starting at index $A[i]$ will be the longest string of first locations.
# 4 The Algorithm

Given a string $X$, we first preprocess $X$ to construct its unordered suffix tree, $ST(X)$. Next, we traverse $ST(X)$ to obtain each of the distinct $k$-prefixes of each suffix, labelling each new $k$-prefix with a unique label, $u_j$, as well as each starting index in $X$ of each suffix that $u_j$ labels a prefix of. Each $k$-prefix is equivalent to the substring obtained by traversing each path of depth $k$ from the root of $ST(X)$.

Next, we initialise $2k$ integer arrays, $A_0, \dots, A_{k-1}$, and $A'_0, \dots, A'_j, A'_{k-1}$, where each array is of size $\lfloor(n-j)/k\rfloor$ for $0 \le j \le k-1$. For each $X[i]$ for $i \in [0 \dots n-k]$, we store the unique label corresponding to the $k$-prefix starting at index $X[i]$ in array $A_{(i \bmod k)}$[$\lfloor i/k \rfloor$]. For each $A'_j[i]$ where $i \in [0, \lfloor(n-j)/k\rfloor-1]$, $0 \le j \le k-1$, we store the index directly to the left of the next occurrence of the element $u_j$ at $A_j[i]$ in $A'_j$. If there is no next occurrence, then $A'_j[i] = |A'_j| - 1$. We make the following two observations:

**Observation 1.** The local maximal $k$-antiperiodic substring of $X[i \dots n-1]$ is the longest subarray of $A_j[m \dots |A_j| - 1]$ where each element only occurs exactly once, where $i = mk + j$, for some $j < k$ and $m \ge 0$.

From Observation 1, each block of $k$ symbols must be distinct to satisfy the antiperiodicity property. Thus, arrays $A'_0, \dots, A'_{k-1}$ are used to record the next occurrence to the right of the $k$-prefix at a given index in arrays $A_0, \dots, A_{k-1}$ so that the end of a $k$-antiperiodic substring occurs one position to the left of this.

An intuitive approach would be to start from the leftmost position of a string and label the first occurrence of an element as $Head_1$ and label the next occurrence of the same element in the string as $Tail_1$. It would then follow that the local maximal antiperiodic substring is bounded between these two occurrences, however one would also need to check that each of the elements between $Head_1$ and $Tail_1$ do not contain any repetitions within these bounds. We can continue to parse the substring between $Head_1$ and $Tail_1$, labelling each first and second occurrences of elements as $Head_j$ and $Tail_j$ (incrementing the value of $j$ for each new pair). In this instance, the longest string of elements only labelled $Head_j$ (starting from $Head_1$) would correspond to a maximal $k$-antiperiodic substring. Otherwise, a substring containing an element labelled $Tail_j$ would indicate the repetition of some factor, thus not satisfying the antiperiodicity requirement. In Fig. 3, we note that if there a repeated element between the first pair of indexes labelled $Head_1$ and $Tail_1$, the end of the maximal $k$-antiperiodic substring would be reduced from the position to the left of $Tail_1$ to the position to the left of $Tail_2$.

Unfortunately, this approach of working left-to-right, has a lot of redundancy as it is possible for reported substrings to be nested in others. For example in Fig. 1, the local maximal 2-antiperiodic substrings starting at $X[1]$, $X[3]$ and $X[5]$ are nested. To avoid re-computing smaller antiperiodic substrings and thereby increasing the runtime of the algorithm, we employ a dynamic programming approach starting from the rightmost position and work right-to-left.
<figure><img src="image_4.png" /><figcaption>**Fig. 3.** Given the string $X = \ell_1\ell_2\ell_3\ell_2\ell_4\ell_1\ell_3$ (where each $\ell_i$ denotes a block of size $k$), the local maximal $k$-antiperiodic substring beginning at position 0 is initially upper bounded to position 4 (by the occurrence of $Tail_1$ at position 5). It follows that $\ell_2$ at position 1 has a second occurrence at position 3, which is smaller than the index of the upper bound, thus the upper bound is updated to position 2.</figcaption></figure>

To this end, we initialise a new array $B_j$ for each $j = 0, \dots, k-1$, where each array is of size $\lfloor(n-j)/k\rfloor$, which will store the position $B_j[i]$ of the first repeated factor that is encountered in $A_j$ starting from position $i$.

We set $B_j[m_j] = m_j$, where $m_j = |B_j| - 1$ is the index of the last element of $B_j$, since this final factor of length $k$ is trivially a local maximal $k$-antiperiodic substring. Next, for all $i = m_j - 1, \dots, 0$, we set

$$B_j[i] = \min(B_j[i+1], A'_j[i] - 1), \quad (1)$$

which is to say that the local maximal $k$-antiperiodic substring starting at position $i$ either terminates in the same position as the local maximal $k$-antiperiodic substring starting at position $(i+1)$ (in the case that $B_j[i+1] \le A'_j[i]$), or else terminates at one position prior to the factor in position $A'_j[i]$, which by definition, is the next repeat of the factor in position $i$.

It is straightforward to show that the sequence $B_j$, as defined by (1), is monotonically increasing, and bounded from below.

**Lemma 1.** (i) We have that $B_j[i] \le B_j[i']$ whenever $i \le i'$.

(ii) We have that $i \le B_j[i]$ for all $i \le m_j$.

*Proof.* Trivial.

We can then use the sequences $B_j$ to identify the local maximal $k$-antiperiodic substrings of our input string $X$ using the following theorem.

**Theorem 2.** For all $j < k$ and $i = 0, \dots, m_j$, we have that $A_j[i..B_j[i]]$ is the local maximal $k$-antiperiodic substring of $X$ of length $k(B_j[i] - (i-1))$ starting at position $(ik + j)$.

*Proof.* Fix $j < k$ and suppose to the contrary that there is some $i \le m_j$ such that $U = A_j[i..B_j[i]]$ is not the local maximal $k$-antiperiodic substring of $X$. Without loss of generality, suppose that $i$ is the largest such value where this contradiction occurs.
- Suppose $U$ is not $k$-antiperiodic, then there is some $i \le \ell, \ell' \le B_j[i]$ such that $A_j[\ell] = A_j[\ell']$. Without loss of generality we may assume that $A_j[\ell']$ is the next repeat of $A_j[\ell]$ after position $\ell$. By definition, we have that $A'_j[\ell] = \ell'$, and hence, by (1), we must have that $B_j[\ell] \le \ell' - 1 < B_j[i]$, contrary to Lemma 1(i).

- Suppose that $B_j[i] \ne m_j$ and that $U$ is not maximal, then $U$ can be extended to a longer $k$-antiperiodic substring by appending $A_j[\ell+1]$, where $\ell = B_j[i]$, which is to say that $A_j[\ell+1] \ne A_j[t]$ for any $t \in \{i, \dots, \ell\}$. But then by definition $A'_j[t] > \ell+1$ for all $t = i, \dots, \ell$. Moreover, we have that $B_j[\ell+1] \ge \ell+1$, by Lemma 1(ii).

It then follows inductively that $B_j[t] \ge \ell+1$ for all $t = i, \dots, \ell$. In particular, we have that the contradiction that $B_j[i] \ge \ell+1 > B_j[i]$, since $\ell = B_j[i]$.

Hence, we must have that $U = A_j[i..B_j[i]]$ is the local maximal $k$-antiperiodic substring of $X$, for all $i < m_j$, as required.

*Example 1.* Consider the string $X = aaabbabbbbbaabaaabbaaa$ and $k = 2$. From the suffix tree of $X$ (displayed in Fig. 2), we obtain each of the distinct 2-prefixes of each suffix as well as their corresponding occurrences (Tables 1, 2 and 3):

<table><caption>**Table 1.** 2-prefixes of $X$.</caption><thead><tr><th>Prefix</th><th>Label</th><th>Occurrences</th></tr></thead><tbody><tr><td>aa</td><td>u<sub>1</sub></td><td>0, 1, 11, 14, 15, 19, 20</td></tr><tr><td>ab</td><td>u<sub>2</sub></td><td>2, 5, 12, 16</td></tr><tr><td>ba</td><td>u<sub>3</sub></td><td>4, 10, 13, 18</td></tr><tr><td>bb</td><td>u<sub>4</sub></td><td>3, 6, 7, 8, 9, 17</td></tr></tbody></table>

Each of the arrays, $A_0, A'_0, A_1, A'_1$ are generated and filled as follows:

<table><caption>**Table 2.** $j = 0$.</caption><thead><tr><th></th><th>0</th><th>1</th><th>2</th><th>3</th><th>4</th><th>5</th><th>6</th><th>7</th><th>8</th><th>9</th><th>10</th></tr></thead><tbody><tr><th>A<sub>0</sub></th><td>u<sub>1</sub></td><td>u<sub>2</sub></td><td>u<sub>3</sub></td><td>u<sub>4</sub></td><td>u<sub>4</sub></td><td>u<sub>3</sub></td><td>u<sub>2</sub></td><td>u<sub>1</sub></td><td>u<sub>2</sub></td><td>u<sub>3</sub></td><td>u<sub>1</sub></td></tr><tr><th>A'<sub>0</sub></th><td>7</td><td>6</td><td>5</td><td>4</td><td>10</td><td>9</td><td>8</td><td>10</td><td>10</td><td>10</td><td>10</td></tr></tbody></table>

<table><caption>**Table 3.** $j = 1$.</caption><thead><tr><th></th><th>0</th><th>1</th><th>2</th><th>3</th><th>4</th><th>5</th><th>6</th><th>7</th><th>8</th><th>9</th></tr></thead><tbody><tr><th>A<sub>1</sub></th><td>u<sub>1</sub></td><td>u<sub>4</sub></td><td>u<sub>2</sub></td><td>u<sub>4</sub></td><td>u<sub>4</sub></td><td>u<sub>1</sub></td><td>u<sub>3</sub></td><td>u<sub>1</sub></td><td>u<sub>4</sub></td><td>u<sub>1</sub></td></tr><tr><th>A'<sub>1</sub></th><td>5</td><td>3</td><td>9</td><td>4</td><td>8</td><td>7</td><td>9</td><td>9</td><td>9</td><td>9</td></tr></tbody></table>

Table 4 reports each of the corresponding instances of $B_j[i]$ for each instance of $A_j[i]$, as well as the corresponding maximal $k$-antiperiodic substring in $X$.

The pseudocode for our algorithm is presented in Algorithm 1.
<table><caption>**Table 4.** Computed instances of $B_j[i]$ for each $A_j[i]$ as well as the corresponding substring of $X = aaabbabbbbbaabaaabbaaaa$.</caption><thead><tr><th>i</th><th>A<sub>0</sub>[i]</th><th>B<sub>0</sub>[i]</th><th>max k-antiperiodic substring in X</th><th>A<sub>1</sub>[i]</th><th>B<sub>1</sub>[i]</th><th>max k-antiperiodic substring in X</th></tr></thead><tbody><tr><td>0</td><td>aa</td><td>B<sub>0</sub>[1] = 3</td><td>X[0..7]</td><td>aa</td><td>B<sub>1</sub>[1] = 2</td><td>X[1..6]</td></tr><tr><td>1</td><td>ab</td><td>B<sub>0</sub>[2] = 3</td><td>X[2..7]</td><td>bb</td><td>2</td><td>X[3..6]</td></tr><tr><td>2</td><td>ba</td><td>B<sub>0</sub>[3] = 3</td><td>X[4..7]</td><td>ab</td><td>B<sub>1</sub>[3] = 3</td><td>X[5..8]</td></tr><tr><td>3</td><td>bb</td><td>3</td><td>X[6..7]</td><td>bb</td><td>3</td><td>X[7..8]</td></tr><tr><td>4</td><td>bb</td><td>B<sub>0</sub>[5] = 7</td><td>X[8..15]</td><td>bb</td><td>B<sub>1</sub>[5] = 6</td><td>X[9..14]</td></tr><tr><td>5</td><td>ba</td><td>B<sub>0</sub>[6] = 7</td><td>X[10..15]</td><td>aa</td><td>6</td><td>X[11..14]</td></tr><tr><td>6</td><td>ab</td><td>7</td><td>X[12..15]</td><td>ba</td><td>B<sub>1</sub>[7] = 8</td><td>X[13..18]</td></tr><tr><td>7</td><td>aa</td><td>9</td><td>X[14..19]</td><td>aa</td><td>8</td><td>X[15..18]</td></tr><tr><td>8</td><td>ab</td><td>10</td><td>X[16..21]</td><td>bb</td><td>9</td><td>X[17..20]</td></tr><tr><td>9</td><td>ba</td><td>10</td><td>X[18..21]</td><td>aa</td><td>9</td><td>X[19..20]</td></tr><tr><td>10</td><td>aa</td><td>10</td><td>X[20..21]</td><td></td><td></td><td></td></tr></tbody></table>

**Algorithm 1. FindLocalMaximal-kAntiperiodicSubstrings (X, k)**

1: $n := \text{length}(X)$
2: $ST_X := \text{MakeSuffixTree}(X)$
3: $DkP_{dict} := \text{GetDistinctkPrefix}(ST_X, k)$
4: **for** $j \in \{0, \dots, k-1\}$ **do**
5: &nbsp;&nbsp;&nbsp;&nbsp;Initialize $A_j := []$, $A'_j := []$
6: &nbsp;&nbsp;&nbsp;&nbsp;**for** prefix in $DkP_{dict}$ **do**
7: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;`last_idx = None`
8: &nbsp;&nbsp;&nbsp;&nbsp;**for** pos in $DkP_{dict}$[prefix] **do**
9: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;`j := pos%k`
10: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;`idx := \lfloor(pos - j)/k\rfloor`
11: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;`A_j[idx] := prefix`
12: &nbsp;&nbsp;&nbsp;&nbsp;**if** `last_idx` $\neq$ `None` **then**
13: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;`A'_j['last_idx'] = idx`
14: &nbsp;&nbsp;&nbsp;&nbsp;`last_idx = idx`
15: **for** $j \in \{0, \dots, k-1\}$ **do**
16: &nbsp;&nbsp;&nbsp;&nbsp;Initialize $B_j := []$
17: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;`i := \lfloor(n - j)/k\rfloor - 1`
18: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;`B_j[i] := i`
19: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;`i := i - 1`
20: **while** $i \ge 0$ **do**
21: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;`B_j[i] := \min(B_j[i+1], A'_j[i] - 1)`
22: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;`i := i - 1`
23: &nbsp;&nbsp;&nbsp;&nbsp;Initialize `localMaxkAntiPerSubstr := []`
24: **for** $i \in \{0, \dots, \lfloor n/k \rfloor\}$ **do**
25: &nbsp;&nbsp;&nbsp;&nbsp;**for** $j \in \{0, \dots, k\}$ **do**
26: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;`start := i \cdot k + j`
27: &nbsp;&nbsp;&nbsp;&nbsp;**if** `start` $< n$ **then**
28: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;`end := B_j[i] \cdot k + j`
29: &nbsp;&nbsp;&nbsp;&nbsp;`localMaxkAntiPerSubstr[i \cdot k + j] := X[start..end]`
30: **return** `localMaxkAntiPerSubstr`
# 5 Analysis of the Algorithm

**Lemma 3.** The length of any maximal *k*-antiperiodic substring is less than or equal to $|\Sigma|^k \mod k$.

*Proof.* Recall that each *k*-antiperiod of a string must be distinct. As there are $|\Sigma|^k$ possible distinct strings of length *k*, the longest possible *k*-antiperiodic string contains every possible distinct substring.

**Theorem 4.** Given a string *X* and integer *k*, all of the local maximal *k*-antiperiod substrings of *X* can be calculated in $O(n)$ time and $O(n)$ space.

*Proof.* We analyse each step of the algorithm as described in Algorithm 1. In (line 2), we first construct the suffix tree of *X*, which requires $O(n)$ time and space to construct [11]. We then create an array with all of the distinct *k*-prefixes of each suffix in the suffix tree — there are at most $O(\min\{n-k+1, |\Sigma|^k \mod k\})$ distinct prefixes, and appending each occurrence of each *k* prefix to the array requires $O(n)$ time and space.

In (lines 4–5), we initialise 2k arrays, $A_0, \dots, A_{k-1}$ and $A'_0, \dots, A'_{k-1}$, each of length $\lfloor n - i/k \rfloor = O(n/k)$, requiring at most $O(n)$ space and time to construct. The outermost loop in (lines 6–14) is called once for each of the $O(\min\{n-k+1, |\Sigma|^k \mod k\})$ distinct prefixes in $DkP_{dict}$. In total, the inner loop in (lines 8–14) collectively loops over all of the $O(n)$ positions in the string $X$, with each of the operations performed in (lines 9–14) taking at most $O(1)$ time (lookup values for $j$ and $idx$ can be pre-computed in $O(n)$ time and space). The innermost while loop in (lines 20–22) is called collectively once for each of the $O(n)$ positions in the string $X$, with the operations performed in (lines 21–22) requiring at most $O(1)$ time. Finally, the innermost loop in (lines 25–29) loops over all $O(n)$ positions in the string $X$, with the operations performed in (lines 24–29) requiring at most $O(1)$ time. Thus, the overall running time and space of the algorithm is $O(n)$, as required.

# 6 Conclusions

We show that given a string *X* and value *k*, all local maximal *k*-antiperiodic substrings can be found in $O(n)$ time and space. The algorithm that we presented can be extended to identify the longest (global) *k*-antiperiodic substring(s) of a given string *X* and integer *k*, which can also be identified in $O(n)$ time and space.

A natural generalisation of our problem would be to identify all local maximal *k*-antiperiodic substrings of a given string for all values of *k* = 2, . . . , *n* − 1. Such an algorithm for this problem would take at least $O(n^2)$ time, as the required number of substrings to report are $O(n^2)$. Instead, we leave the following open problem: given a string *X*, return each of the longest *k*-antiperiodic substrings for *k* = 2, 3, . . . , *n* − 1.
References

1. Alamro, H., Badkobeh, G., Belazzougui, D., Iliopoulos, C.S., Puglisi, S.J.: Computation the antiperiod (s) of a string. In: 30th Annual Symposium on Combinatorial Pattern Matching (CPM 2019). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik (2019)

2. Alzamel, M., et al.: Online algorithms on antipowers and antiperiods. In: Brisaboa, N.R., Puglisi, S.J. (eds.) String Processing and Information Retrieval, pp. 175–188. Springer International Publishing, Cham (2019)

3. Badkobeh, G., Fici, G., Puglisi, S.J.: Algorithms for anti-powers in strings. Inf. Process. Lett. 137, 57–60 (2018)

4. Bannai, H., et al.: Diverse palindromic factorization is NP-complete. In: Potapov, I. (ed.) DLT 2015. LNCS, vol. 9168, pp. 85–96. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-21500-6\_6

5. Bulteau, L., et al.: Multivariate algorithmics for NP-hard string problems. Bulletin of EATCS 3(114) (2014)

6. Burcroff, A.: (k, λ)-anti-powers and other patterns in words. Electron. J. Comb. 25(P4.41) (2018)

7. Condon, A., Maňuch, J., Thachuk, C.: Complexity of a collision-aware string partition problem and its relation to oligo design for gene synthesis. In: Hu, X., Wang, J. (eds.) COCOON 2008. LNCS, vol. 5092, pp. 265–275. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-69733-6\_27

8. Condon, A., Maňuch, J., Thachuk, C.: The complexity of string partitioning. J. Discrete Algorithms 32, 24–43 (2015)

9. Cox, J.C., Lape, J., Sayed, M.A., Hellinga, H.W.: Protein fabrication automation. Protein Sci. 16(3), 379–390 (2007)

10. Defant, C.: Anti-power prefixes of the Thue-Morse word. Electron. J. Comb. 24 (2017)

11. Farach, M.: Optimal suffix tree construction with large alphabets. In: Foundations of Computer Science, 1997. Proceedings., 38th Annual Symposium on, pp. 137–143. IEEE (1997)

12. Fici, G., Restivo, A., Silva, M., Zamboni, L.Q.: Anti-powers in infinite words. J. Comb. Theory, Ser. A 157, 109–119 (2018)

13. Gaetz, M.: Anti-power *j*-fixes of the thue-morse word. Discrete Math. Theoretical Comput. Sci. 23 (2021)

14. Kociumaka, T., Kubica, M., Radoszewski, J., Rytter, W., Waleń, T.: A linear time algorithm for seeds computation. In: Proceedings of the Twenty-third Annual ACM-SIAM Symposium on Discrete algorithms, pp. 1095–1112. SIAM (2012)

15. Kociumaka, T., Radoszewski, J., Rytter, W., Straszyński, J., Waleń, T., Zuba, W.: Efficient representation and counting of antipower factors in words. Inf. Comput. 286, 104779 (2022)

16. Stemmer, W.P., Crameri, A., Ha, K.D., Brennan, T.M., Heyneker, H.L.: Single-step assembly of a gene and entire plasmid from large numbers of oligodeoxyribonucleotides. Gene 164(1), 49–53 (1995)

17. Thue, A.: Uber unendliche zeichenreihen. Norske Vid Selsk. Skr. I Mat-Nat Kl. (Christiana) 7, 1–22 (1906)