Minimal Generators in Optimal Time

For $i,j\in \mathbb{Z}$, we write $[i,j]=[i,j+1)=(i-1,j]=(i-1,j+1)$ to denote the integer range $\{i,i+1,\mathrm{\dots },j\}$ (or the empty set if $i>j$). Let $n\in \mathbb{N}$. A string $T$ of length $\left|T\right|=n$ is a sequence $T[1]T[2]\mathrm{\dots }T[n]$ of symbols from an alphabet $\mathrm{\Sigma }$ (or the empty string $ϵ$ if $n=0$). We simply write $T[1..n]$ to denote that $T$ is a string of length $n$. Every pair $i,j\in [1,n]$ defines a substring $T[i..j]=T[i..j+1)=T(i-1..j]=T(i-1..j+1)=T[i]T[i+1]\mathrm{\dots }T[j]$ (which equals $ϵ$ if $i>j$). Index $i$ is the position of substring $T[i..j]$. A substring $T[1..i]$ is a prefix of $T$, while a substring $T[i..n]$ is a suffix of $T$. The reversal of $T$ is defined as $\tilde{T}=\text{rev}(T)=T[n]T[n-1]\mathrm{\dots }T[1]$. Another string $S[1..m]$ is a substring of $T$ if there is $i\in [1,n-m+1]$ such that $S[1..m]=T[i..i+m)$, i.e., $\forall j\in [1,m]:T[i+j-1]=S[j]$. From now on, we use $T$ and $S$ to respectively denote the input and output string, and $\alpha ,\beta ,\gamma ,\delta$ to denote intermediate strings. We use the terms string and array interchangeably.

Palindromes, i.e., strings that satisfy $\alpha =\tilde{\alpha }$, are essential for the study of minimal generators. A fundamental tool for detecting palindromic substrings is Manacher’s algorithm [19]. It computes, for each position $i\in [1,n]$ of $T$, the maximal radius $\mathrm{\ell }\in [0,\min (i-1,n-i)]$ such that $T[i-\mathrm{\ell }..i+\mathrm{\ell }]$ is a palindrome in overall $𝒪(n)$ time. Note that, while not strictly required, familiarity with the details of Manacher’s algorithm will be beneficial for understanding the new algorithm for computing minimal generators.

An oracle string $T[1..n]$ can only be accessed via the following type of oracle query. Given query positions $i,j\in [1,n]$, the oracle answers if $T[i]=T[j]$. Algorithms that receive an oracle string as input are more commonly described as working over general (unordered) alphabet, or as accessing the input via equality comparisons. We present algorithms that (apart from the oracle queries) work in the word RAM model, i.e., they perform an interleaved sequence of oracle queries and word RAM operations. The time complexity of an algorithm is the sum of the number of oracle queries and the number of word RAM operations performed. The size of a machine word is assumed to be at least ${\log }_{2}n$ bits.

Since an oracle string has no physical representation, it is not obvious how to perform traditional string operations like extracting, deleting, or overwriting substrings. We allow such operations by wrapping the input oracle string $T[1..n]$ as follows. Every string $S[1..m]$ encountered during the algorithm execution (e.g., a substring extracted from $T$ or the computed output string) is physically represented by an array $A\in {[1,n]}^m$, indicating that $\forall i\in [1,m]:S[i]=T[A[i]]$. This also holds for the input string $T[1..n]$ itself, which is represented by $B[1..n]$ with $\forall i\in [1,n]:B[i]=i$. Hence we can perform operations that modify or create copies of (sub)strings directly on the physical representations. Given the physical representations, we can still perform any symbol comparison in constant time with a single oracle query to $T[1..n]$. We hide this additional level of complexity from now on.

Let $S[1..m]$ be a string, and let $n\in {\mathbb{N}}^{+}$. Then $f:[1,n]\to [1,m]$ is a walk on $S$ if and only if $\forall i\in [2,n]:\left|f(i)-f(i-1)\right|\le 1$. The walk $f$ on $S$ generates the string $T[1..n]$ defined by $\forall i\in [1,n]:T[i]=S[f(i)]$. More generally, a string $S$ generates another string $T$ if and only if there is a walk on $S$ that generates $T$. We further say that $S$ generates $T$ from left to right if and only if there is a walk $f$ on $S$ that generates $T$ with $f(1)=1$ and $f(\left|T\right|)=\left|S\right|$. Trivially, if $S$ generates $T$ from left to right, then $\left|S\right|\le \left|T\right|$. The following properties are straight-forward. (The first one is obtained by composing the two generating walks, the second one by concatenating them.)

A minimal generator of $T$ is a string that generates $T$ and is of minimal length (i.e., there is no shorter generator). The minimal generator of $T$ is unique up to reversal [22]. Whether or not a generator is minimal can be characterized by using the following types of substrings. A (non-trivial) palindrome is a string $y$ (of length at least two) such that $y=\tilde{y}$. A twin-palindrome is a string of the form $axb\tilde{x}axb$ for symbols $a,b$ and a string $x$. A unit-square is a string of the form $aa$ for a symbol $a$.

Particularly, a minimal generator can be obtained from $T$ by repeatedly applying the following substitutions until no further substitutions are possible. (The correctness is straight-forward, see Observation 2 and the proof of [22, Lemma 6]).

Our algorithm for computing the minimal generator performs the following three steps. First, we eliminate all unit-squares by applying Lemma 4(i) until no longer possible. Second, we eliminate twin-palindromes by applying Lemma 4(ii) until no longer possible, which introduces no new substrings of length two, and thus no new unit-squares. Third, we eliminate non-trivial suffix and prefix palindromes by applying Lemma 4(iii) until no longer possible. This introduces no new substrings, and thus the string remains free of unit-squares and twin-palindromes. The first and third step are easily performed using the auxiliary lemmas below. In the remainder of the paper, we focus on the elimination of twin-palindromes in the second step, for which we make the following observation.

We start with $\beta =\alpha [1]$. For each $i\in [2,n]$ in increasing order, we append $\alpha [i]$ to $\beta$ if and only if $\alpha [i]\ne \alpha [i-1]$, which clearly takes $𝒪(n)$ time and yields the desired result. $◀$

We start with a copy of $T$ and modify it as follows. As long as there is a non-trivial prefix palindrome $xa\tilde{x}$, we replace it with $a\tilde{x}$. Then, as long as there is a non-trivial suffix palindrome $xa\tilde{x}$, we replace it with $xa$. (In both cases, $a$ is a symbol and $x$ is a non-empty string.) This results in a generator of $T$ by Lemma 4(iii). Note that neither of the replacements introduces any new substrings because they merely truncate the string. Hence we introduce no new unit-squares or twin-palindromes, and the resulting string must be a minimal generator of $T$ by Lemma 3.

We will find a non-trivial prefix or suffix palindrome $xa\tilde{x}$ in $𝒪(x)$ time, or determine that none exists is $𝒪(n)$ time. Whenever we spend $𝒪(x)$ time to discover a prefix or suffix palindrome, we also reduce the length of the string by $x$, and thus the time sums to $𝒪(n)$.

It remains to show how to find a prefix palindrome $xa\tilde{x}$. We proceed in up to $\lceil {\log }_{2}n\rceil$ phases. In phase $j$ (starting with $j=1$), we aim to find a prefix palindrome of length in range $(2^{j-1},2^j]$. We run Manacher’s algorithm [19] and find the longest prefix palindrome of $T[1..\min (n,2^j)]$ in $𝒪(2^j)$ time. If it is non-trivial, then it is of length at least $2^{j-1}$, since otherwise we would have discovered it in an earlier phase. Also, its length must be odd because $T$ is free of unit-squares (and even-length palindromes contain a unit-square at their center). As soon as we find a non-trivial prefix palindrome, we report it and perform no further phases. If we discover a non-trivial prefix palindrome in phase $j$, then the time sums to $𝒪(2^j)$, which is linear in the length of the palindrome. Otherwise, we finish all phases in $𝒪(n)$ time and there is no non-trivial palindromic prefix. The procedure for suffix palindromes is symmetric. $◀$

Assume that $T$ contains no unit-squares. This assumption is without loss of generality, as otherwise we can eliminate unit-squares with Lemma 6, and then show the correctness of the Corollary for the resulting shorter string. We terminate in constant time if $n=1$. Otherwise, we recursively apply the Corollary to $T_1=T[1..\lfloor \frac{n}{2}\rfloor ]$ and $T_2=T(\lfloor \frac{n}{2}\rfloor ..n]$, resulting in strings $T_1^{\prime }$ and $T_2^{\prime }$ that contain neither twin-palindromes nor unit-squares. Furthermore, $T_1^{\prime }$ generates $T_1$ from left to right, and $T_2^{\prime }$ generates $T_2$ from left to right. Hence, by Observation 2(ii), $T_1^{\prime }{T}_2^{\prime }$ generates $T$ from left to right. We apply Theorem 8 with $k=n$ to $T_1^{\prime }$ and $T_2^{\prime }$. In $𝒪(n)$ time, we obtain $n^{\prime }\in [0,\left|T_1^{\prime }\right|]$ and $m^{\prime }\in [0,\left|T_2^{\prime }\right|]$ such that $S=T_1^{\prime }[1..n-n^{\prime }]T_2^{\prime }(m^{\prime }..|T_2^{\prime }|]$ generates $T_1^{\prime }{T}_2^{\prime }$ (and by Observation 2(i) also $T$) from left to right. Furthermore, $S$ contains no unit-squares or twin-palindromes. We spend $𝒪(n)$ time per level of recursion, and $𝒪(n\log n)$ time overall. $◀$

Now we prove Theorem 8. We start with an algorithm for finding a shortest twin-palindromic substring (or verifying that none exist) in linear time. At first glance, prioritizing short twin-palindromes might seem counter-intuitive; one might expect that long twin-palindromes should be eliminated early to quickly reduce the size of the input. However, finding long twin-palindromes appears to be more challenging, and finding the shortest one still suffices for proving Theorem 8.

We compute the maximal radius $R[i]$ of a palindrome centered at each $i\in [1,n]$, i.e., $R[i]=\max \{h\in [0,\min (i-1,n-i)]\mid \alpha [i-h..i+h]\text{ is a palindrome}\}$. A twin-palindrome must be of length $3k+1$ for some positive integer $k$. Fix $k$ and consider a substring $\alpha [p..p+3k]$. Observation 5 states that $\alpha [p..p+3k]$ is a twin-palindrome if and only if $\alpha [p..p+2k]$ and $\alpha [p+k..p+3k]$ are palindromes, which is the case if and only if $R[p+k]\ge k$ and $R[p+2k]\ge k$. This dictates a simple algorithm for detecting all twin-palindromes. We consider each pair $\mathrm{\ell },r\in [1,n]$ with . Let $k=r-\mathrm{\ell }$ and $p=\mathrm{\ell }-k$, which implies $\mathrm{\ell }=p+k$ and $r=p+2k$. If $R[\mathrm{\ell }]\ge k$ and $R[r]\ge k$, then we report $\alpha [p..p+3k]$ as a twin-palindrome. There are $\mathrm{\Theta }(n^2)$ pairs, and each pair is processed in constant time.

We cannot afford to consider each pair of positions. Hence we show that $𝒪(n)$ pairs are sufficient to detect a shortest twin-palindrome. Let $\alpha [p..p+3k]$ be any such twin-palindrome, i.e., $\alpha$ contains no twin-palindrome of length less than $3k+1$. Let $\mathrm{\ell }=p+k$ and $r=p+2k$. We already know that $R[\mathrm{\ell }]\ge k$ and $R[r]\ge k$. We claim that . Indeed, $R[m]\ge k$ with $m\in (\mathrm{\ell },r)$ implies that $\alpha [\mathrm{\ell }..2m-\mathrm{\ell }]$ is a palindrome of length $2(m-\mathrm{\ell })+1$ centered at position $m$. Due to $R[\mathrm{\ell }]\ge k>m-\mathrm{\ell }$, we know that $\alpha [2\mathrm{\ell }-m..m]$ is a palindrome of length $2(m-\mathrm{\ell })+1$ centered at position $\mathrm{\ell }$. Thus, Observation 5 implies that $\alpha [2\mathrm{\ell }-m..2m-\mathrm{\ell }]$ is a twin-palindrome of length . However, this contradicts the fact that $\alpha$ contains no twin-palindrome of length less than $3k+1$.

Now we exploit the new insights algorithmically. For each position $i\in [1,n]$, we compute $\text{prv}[i]=\max (\{j\in [1,i)\mid R[j]\ge R[i]\}\cup \{0\})$ and $\text{nxt}[i]=\min (\{j\in (i,n]\mid R[j]\ge R[i]\}\cup \{n+1\})$, i.e., the positions of the previous and next non-smaller value of $R[i]$ in $R$. For a shortest twin-palindrome $\alpha [p..p+3k]$ with $\mathrm{\ell }=p+k$ and $r=p+2k$, we have shown that $R[\mathrm{\ell }]\ge k$, $R[r]\ge k$, and . Hence either $\text{nxt}[\mathrm{\ell }]=r$ or $\text{prv}[r]=\mathrm{\ell }$ (or both). Thus, instead of processing all the $\mathrm{\Theta }(n^2)$ possible pairs of positions, we instead process only the $𝒪(n)$ pairs $\{(\mathrm{\ell },\text{nxt}[\mathrm{\ell }])\mid \mathrm{\ell }\in [1,n]\text{ and }\text{nxt}[\mathrm{\ell }]\le n\}\cup \{(\text{prv}[r],r)\mid r\in [1,n]\text{ and }\text{prv}[r]>0\}$. If no twin-palindrome is found, we report that $\alpha$ contains no twin-palindrome. Otherwise, among the discovered twin-palindromes, we choose and report one of minimal length. Given $R$, nxt, and prv, we can generate and process the pairs in $𝒪(n)$ time. Computing $R$ takes $𝒪(n)$ time with Manacher’s algorithm [19]. Computing nxt and prv takes $𝒪(n)$ time with a simple folklore algorithm (see, e.g., [5, Lemma 1]). $◀$

Given two strings that contain no twin-palindromes (possibly substrings of a longer string, in the representation described in Section 2), we can use the Lemma above to find a twin-palindrome in their concatenation. Most importantly, this yields an output-sensitive algorithm: if the algorithm reports a twin-palindrome, its runtime is linear in the length of that twin-palindrome; otherwise, the runtime is linear in the combined length of the input strings. This property will later allow us to amortize the time over the number of symbols removed from the input when computing the minimal generator.

Similarly to Lemma 7, we proceed in up to $\lceil {\log }_2(n+m)\rceil$ phases. In phase $j$ (starting with $j=1$), we aim to find a twin-palindrome $\alpha (n-n^{\prime }..n]\beta [1..m^{\prime }]$ with $n^{\prime }+m^{\prime }\in (2^{j-1},2^j]$. As soon as we find such $n^{\prime },m^{\prime }$, we return them without executing further phases. We will perform phase $j$ in $𝒪(2^j)$ time. Hence, if we find $n^{\prime },m^{\prime }$ in phase $j$, the total time sums to $𝒪(2^j)$, which is $𝒪(n^{\prime }+m^{\prime })$ due to $n^{\prime }+m^{\prime }\in (2^{j-1},2^j]$. If all phases finish without finding $n^{\prime },m^{\prime }$, then the time sums to $𝒪(2^{\lceil {\log }_2(n+m)\rceil })=𝒪(n+m)$.

It remains to show how to perform phase $j$ in $𝒪(2^j)$ time. Since we aim to find $n^{\prime },m^{\prime }\le 2^j$, it suffices to consider ${\alpha }^{\prime }=\alpha [\max (1,n-2^j+1),n]$ and ${\beta }^{\prime }=\beta [1..\min (m,2^j)]$ of total length $𝒪(2^j)$. We apply Lemma 10 to $\gamma ={\alpha }^{\prime }{\beta }^{\prime }$ in $𝒪(2^j)$ time. Since ${\alpha }^{\prime }=\gamma [1..\min (n,2^j)]$ and ${\beta }^{\prime }=\gamma (\min (n,2^j)..|\gamma |]$ are free of twin-palindromes, every twin-palindrome $\gamma (a..b]$ satisfies . Hence, if Lemma 10 reports $\gamma (a..b]$ as a twin-palindrome, we return $n^{\prime }=\min (n,2^j)-a$ and $m^{\prime }=b-\min (n,2^j)$. Note that $b-a>2^{j-1}$, since otherwise the twin-palindrome would have already been discovered during the previous phase. If Lemma 10 reports no twin-palindrome, then ${\alpha }^{\prime }{\beta }^{\prime }$ contains no twin-palindrome. $◀$

We are now ready to show Theorem 8. The algorithm first finds a twin-palindrome of length $\mathrm{\ell }\le k$ crossing the boundary between $\alpha$ and $\beta$. By Lemma 11, this step takes either $𝒪(\mathrm{\ell })$ time if the twin-palindrome exists, or $𝒪(k)$ time otherwise. If over half of the twin-palindrome is in $\alpha$ (resp., $\beta$), the algorithm cuts its left (resp., right) part out of $\alpha$ and $\beta$ shortening them by $\mathrm{\Omega }(\mathrm{\ell })$ symbols, and applies the algorithm recursively to the resulting strings $\alpha$ and $\beta$. As a result, the total time is linear in the sum of $k$ and on the number of the symbols that were cut off.

See 8

If at least one of the strings is empty, then we trivially return $n^{\prime }=m^{\prime }=0$. If neither $\alpha$ nor $\beta$ contain unit-squares, then we can without loss of generality assume that $\alpha \beta$ contains no unit-squares. This is because the only possible unit-square in $\alpha \beta$ is $\alpha [n]\beta [1]$, and if $\alpha [n]=\beta [1]$ we can simply run the algorithm for $\alpha$ and $\beta [2..m]$ instead.

If both strings are non-empty, we apply Lemma 11 to ${\alpha }_0=\alpha (\max (0,n-k)..n]$ and ${\beta }_0=\beta [1..\min (m,k)]$. This either results in $n_0\in [1,\min (n,k)]$ and $m_0\in [1,\min (m,k)]$ such that $\alpha (n-n_0..n]\beta [1..m_0]$ is a twin-palindrome in $𝒪(n_0+m_0)$ time, or determines that no such values exist in $𝒪(k)$ time. Since $\alpha$ and $\beta$ do not contain any twin-palindromes of length at most $k$, it is clear that $\alpha \beta$ contains no twin-palindrome of length at most $k$ if and only if no values $n_0,m_0$ are found. Hence, if no values are found, we output $n^{\prime }=m^{\prime }=0$.

Otherwise, there are symbols $a,b$ and a string $x$ such that $\alpha (n-n_0..n]\beta [1..m_0]=axb\tilde{x}axb$. Let $h=\left|axb\right|\le (n_0+m_0)/2$. Assume that $n_0\ge m_0$, then it holds $h\le n_0$ and $\alpha (n-n_0..n-n_0+h]=axb$. By Lemma 4(ii), ${\alpha }_1{\beta }_1$ with ${\alpha }_1=\alpha [1..n-n_0+h]$ and ${\beta }_1=\beta (m_0..m]$ generates $\alpha \beta$ from left to right. Similarly, if , then and $\beta (m_0-h..m_0]=axb$. In this case, again by Lemma 4(ii), ${\alpha }_1{\beta }_1$ with ${\alpha }_1=\alpha [1..n-n_0]$ and ${\beta }_1=\beta (m_0-h..m]$ generates $\alpha \beta$ from left to right. Either way, $h\le (n_0+m_0)/2$ implies $\left|{\alpha }_1{\beta }_1\right|=n+m-n_0-m_0+h\le n+m-(n_0+m_0)/2.$

We finish the computation by applying Theorem 8 recursively to ${\alpha }_1$ and ${\beta }_1$ (where we do not need to materialize ${\alpha }_1$ and ${\beta }_1$, as they are respectively a prefix and a suffix of $\alpha$ and $\beta$). This results in values $n_1$ and $m_1$ such that ${\alpha }_1[1..|{\alpha }_1|-n_1]{\beta }_1(m_1..|{\beta }_1|]$ generates ${\alpha }_1{\beta }_1$ from left to right and contains no twin-palindrome of length at most $k$. We have already established that ${\alpha }_1{\beta }_1$ generates $\alpha \beta$ from left to right, and hence also ${\alpha }_1[1..|{\alpha }_1|-n_1]{\beta }_1(m_1..|{\beta }_1|]$ generates $\alpha \beta$ from left to right due to Observation 2(i). Thus, we return $n^{\prime }=n-\left|{\alpha }_1\right|+n_1$ and $m^{\prime }=m-\left|{\beta }_1\right|+m_1$. Note that we obtained ${\alpha }_1{\beta }_1$ by replacing $axb\tilde{x}axb$ with $axb$ in $\alpha \beta$. This clearly does not introduce any new substrings of length two, and thus, if $\alpha \beta$ contains no unit-square, then neither does ${\alpha }_1{\beta }_1$, and (recursively) neither does ${\alpha }_1[1..|{\alpha }_1|-n_1]\beta (m_1..|{\beta }_1|]=\alpha [1..n-n^{\prime }]\beta (m^{\prime }..m]$.

Recursively applying the Theorem to ${\alpha }_1$ and ${\beta }_1$ takes $𝒪(k+n_1+m_1)$ time. (This is true by induction over the sum of output values, as we have already shown the correctness for the base case where $n^{\prime }=m^{\prime }=0$.) Apart from that, we spend $𝒪(n_0+m_0)$ time, dominated by applying Lemma 11. The total time is $𝒪(k+n_0+n_1+m_0+m_1)$, which is $𝒪(k+n-\left|{\alpha }_1\right|+n_1+m-\left|{\beta }_1\right|+m_1)=𝒪(k+n^{\prime }+m^{\prime })$ due to $\left|{\alpha }_1{\beta }_1\right|\le n+m-(n_0+m_0)/2$. $◀$

For both properties, we only have to consider palindromes of odd length because $\alpha$ contains no unit-square, and every palindrome of even length contains a unit-square at its center. For (i), assume that $\alpha$ has two non-trivial palindromic suffixes of respective lengths $2k_1+1$ and $2k_2+1$ such that $k_2\in (k_1,2k_1]$. Let $\mathrm{\ell }=k_2-k_1\le k_1$. Then $\alpha [n-2k_1..n]$ is a palindrome centered at position $n-k_1$, and its central portion of length $2\mathrm{\ell }+1$ is $\alpha [n-k_1-\mathrm{\ell }..n-k_1+\mathrm{\ell }]=\alpha [n-k_2..n-k_2+2\mathrm{\ell }]$. Similarly, $\alpha [n-2k_2..n]$ is a palindrome centered at $n-k_2$, and its central portion of length $2\mathrm{\ell }+1$ is $\alpha [n-k_2-\mathrm{\ell }..n-k_2+\mathrm{\ell }]$. However, by Observation 5, if $\alpha [n-k_2..n-k_2+2\mathrm{\ell }]$ and $\alpha [n-k_2-\mathrm{\ell }..n-k_2+\mathrm{\ell }]$ are palindromes, then $\alpha [n-k_2-\mathrm{\ell }..n-k_2+2\mathrm{\ell }]$ is a twin-palindrome, which is a contradiction. (See Figure 1(a).) Therefore, if we consider all the non-trivial palindromic suffixes in increasing order of length, then each suffix must be over twice as long as the previous one, and hence their number is $𝒪(\log n)$.

For (ii), let $m=n+1$ and $\beta [1..m]=\alpha \cdot b$. Let $k_2$ be chosen such that $\beta [m-2k_2..m]$ is the longest palindromic suffix of $\beta$. If $\beta$ has some twin-palindromic suffix $\beta [m-3k_1..m]$, then it also has palindromic suffix $\beta [m-2k_1..m]$, which implies $k_1\le k_2$. If $k_1=k_2$, then $\beta [m-3k_1..m]$ is the claimed unique twin-palindromic suffix. It remains to consider the case $k_1>k_2$. In a moment, we will show that $k_1>k_2$ implies , i.e., the twin-palindromic suffix $\beta [m-3k_1..m]$ is of length less than $2k_2$. However, due to the palindromic suffix $\beta [m-2k_2..m]$, it holds $\beta [m-2k_2..m-2k_2+3k_1]=\text{rev}(\beta [m-3k_1..m])$. The reversal of a twin-palindrome is also a twin-palindrome, and thus $\beta [m-2k_2..m-2k_2+3k_1]$ is a twin-palindromic substring of $\alpha =\beta [1..m)$ (particularly due to ; see Figure 1(b)). This contradicts the fact that $\alpha$ contains no twin-palindromes.

Finally, we show that $k_1>k_2$ indeed implies . If $k_1>1$, then we observe that $\alpha$ has non-trivial suffix palindromes of respective lengths $2k_1-1=2(k_1-1)+1$ and $2k_2-1=2(k_2-1)+1$ (by truncating the palindromes $\beta [m-2k_1..m]$ and $\beta [m-2k_2..m]$ by one symbol on either side). As seen in the proof of (i), it holds $k_2-1\notin (k_1-1,2k_1-2]$. This implies $k_2\ge 2k_1$, which in turn implies . (The latter inequality is due to and thus $k_2\ge 3$.) If $k_1=1$, then the twin-palindromic suffix at hand is $\beta [m-3..m]=\alpha [m-3..m)\cdot b=abab$ with $a=\alpha [m-1]$. If $k_2=2$ then $\beta [m-4..m]=babab$. However, then $\alpha$ has twin-palindromic suffix $\alpha [m-3..m)=baba$, which is a contradiction. Hence $k_2>2$, which implies . $◀$

Let $s=\lceil {({\log }_{2}n)}^2\rceil$. We use a modified version of Manacher’s algorithm for maximal palindromic substrings [19]. In each step, the algorithm maintains the following data structures:

1. (1)

   Strings $\alpha [1..a]$ and $\beta [1..b]$ are the current working strings such that

   1. (i)

      $\alpha \beta$ generates $T$ from left to right, and

   2. (ii)

      $\alpha \beta$ contains neither unit-squares nor twin-palindromes of length less than $s$, and

   3. (iii)

      $\alpha$ contains no twin-palindromes.

2. (2)

   List $C=[c_1,c_2,\mathrm{\dots },c_q]$ with stores a subset of $[1,a]$ such that

   1. (i)

      if $c\in [1,a]$ is the center of a palindromic suffix of $\alpha$, then $c$ is in $C$ (but not every element of $C$ is necessarily the center of a palindromic suffix of $\alpha$), and

   2. (ii)

      $c_1$ is the center of the longest palindromic suffix of $\alpha$ (hence $C$ is non-empty).

3. (3)

   A prefix of array $R[1..n]$ contains, for each $i\in [1,a]\setminus \{c_1,c_2,\mathrm{\dots },c_q\}$, the maximal radius of a palindrome centered at position $i$ with respect to $\alpha$, i.e.,

   $$R[i]=\max \{h\in [0,\min (i-1,a-i)]\mid \alpha [i-h..i+h]\text{ is a palindrome}\}.$$

4. (4)

   A prefix of array $E[1..n]$ contains, for each $j\in [1,a]$, a list of centers defined as follows. The list $E[j]$ contains exactly all the $i\in [1,a]\setminus \{c_1,c_2,\mathrm{\dots },c_q\}$ for which $i+R[i]=j$. (Informally, we store each center at the end position of its maximal palindrome.)

We initialize the algorithm with $\alpha =T[1]$, $\beta =T[2..n]$, and $C=[c_1]$ with $c_1=1$. Without loss of generality, we assume that $T[1]$ has no occurrence in $T[2..n]$ (which can be achieved by prepending a unique symbol in front of $T$). This will ensure that $\alpha$ never becomes empty. Now we alternate between appending a symbol and eliminating twin-palindromes. Appending a symbol means that we remove the first symbol of $\beta$ and append it as the last symbol of $\alpha$, i.e., we replace $\alpha$ with $\alpha \cdot \beta [1]$, and $\beta$ with $\beta [2..b]$. Since their concatenation $\alpha \beta$ does not change, Properties (1i) and (1ii) remain satisfied. As part of the appending routine, we update $C$, $R$, and $E$ so that they satisfy Properties (2), (3), and (4), which we describe in detail below. Afterwards, only Property (1iii) is possibly not satisfied, i.e., it might be that the new $\alpha$ contains a twin-palindrome. In this case, the eliminating subroutine truncates possibly both $\alpha$ and $\beta$ and updates $C$, $R$, and $E$ so that all properties are satisfied. If $\beta$ is empty after running the eliminating subroutine, then $\alpha$ generates $T$ from left to right and contains neither twin-palindromes nor unit-squares.