Covers in Optimal Space

Covers have been investigated in many computational settings and numerous variations have been introduced (for a comprehensive recent survey, see Mhaskar and Smyth [27]). As previously mentioned, the best algorithm for computing all covers of an input string over general alphabet is by Moore and Smyth [28, 29], who presented an $O(n)$ time algorithm. Li and Smyth  [26] consider the more general problem of computing the longest cover of each prefix of $S$, providing an $O(n)$ time algorithm for this problem. Crochemore et al.  [12] considered the problem of constructing an efficient data structure reporting the shortest cover or all covers of a query substring. That is, they show how to preprocess a string in $O(n\log n)$ time to construct an $O(n\log n)$-space data structure that can report the shortest cover of an input substring in $O(\log n\log \log n)$ time.

The study of covers has led to the introduction of numerous variations and generalizations. A $2$-cover of $S$ ([18, 33]) is a pair $(X,Y)$ of strings, such that every index in $S$ is covered either by an occurrence of $X$ or by an occurrence of $Y$. This can be generalized for a $\lambda$-cover, which is a set of $\lambda$ strings that, together, cover every index in $S$. While computing all $\lambda$-covers of a string is NP-complete for general $\lambda$ ([11]), efficient algorithms have been recently introduced for computing $2$-covers ([31, 7]). Charalampopoulos et al. [10] introduced natural notions of covers in 2-dimensional strings, and provided efficient algorithms to compute all such covers of an input 2-dimensional string. Other variations of covers that were introduced and studied are enhanced covers [14], approximate covers [1], Cyclic Covers [16, 19], and Tree Covers [30, 24].

We use bracket notation to denote consecutive sets of integers, i.e. for two integers $i,j$ we denote $[i..j]=\{i,i+1,\mathrm{\dots },j\}$. For a positive integer $n$, we denote $[n]=[1..n]$. An arithmetic progression of integers is a set defined by a triplet of the first element, the difference between elements and the number of elements. We denote it by $\mathrm{𝖠𝖯}({\mathrm{\ell }}_{\min },p,m)=\{{\mathrm{\ell }}_{\min }+k\cdot p\mid k\in [0,m-1]\}$.

A string $S=S[1]S[2]S[3]\mathrm{\dots }S[n]$ of length $|S|=n$ is a sequence of symbols over some alphabet $\mathrm{\Sigma }$. For $i\le j$, $S[i..j]=S[i]S[i+1]\mathrm{\dots }S[j]$ is a substring of $S$. If $i=1$ it is a prefix, and if $j=n$ it is a suffix. A string that appears in $S$ both as a prefix and as a suffix is called a border. A positive integer $p$ is called a period of $S$ if $S[i]=S[i+p]$ for every $i\in [1..n-p]$. The minimal period of $S$ is called the period of $S$. We say that $S$ is periodic, if the period of $P$ is at most $|S|/2$.

For two strings $S$ and $P$ of lengths $n$ and $m$, we say that $P$ occurs at index $i\in [1..n-m+1]$ of $S$ if $P=S[i..i+m-1]$. We call the index $i$ an occurrence of $P$ in $S$. For an index $i\in S$, we say that $i$ is covered by a string $C$ of length $c$ if there is an occurrence of $C$ in $[i-c+1..i]$. If every index in $[1..n]$ in $S$ is covered by $C$, we say that $C$ is a cover of $S$.

Each prefix $S[1..\mathrm{\ell }]$ can be uniquely represented by its length $\mathrm{\ell }$. We say that $\mathrm{\ell }$ is a border-length if $S[1..\mathrm{\ell }]$ is a border of $S$ and cover-length if $S[1..\mathrm{\ell }]$ is a cover of $S$. $\mathrm{𝖡𝗈𝗋𝖽𝖾𝗋𝗌}(S)=\{\mathrm{\ell }\mid S[1..\mathrm{\ell }]\text{ is a border}\}$ similarly $\mathrm{𝖢𝗈𝗏𝖾𝗋𝗌}(S)=\{\mathrm{\ell }\mid S[1..\mathrm{\ell }]\text{ is a cover}\}$. Since every cover must cover index $1$, it must be a prefix of $S$, and since it must cover index $n$, it must also be a suffix of $S$. Therefore, every cover is a border, i.e $\mathrm{𝖢𝗈𝗏𝖾𝗋𝗌}(S)\subseteq \mathrm{𝖡𝗈𝗋𝖽𝖾𝗋𝗌}(S)$.

We assume that the input string is given in a read-only format, meaning the algorithm can query $S[i]$ in constant time but cannot modify the string. In this model, the input string does not occupy $O(n)$ space explicitly, allowing for algorithms with sublinear space complexity. Therefore, the space complexity of the algorithm consists of the working space of the algorithm and of the space dedicated to writing the output. Our algorithm operates in the word RAM model under the standard assumption that both an index from $[n]$ and a symbol from $\mathrm{\Sigma }$ fit within a single machine word.

As a subroutine, our algorithm uses a pattern matching algorithm that uses $O(1)$ space [15]. The algorithm is formally stated in the following lemma.

Here are several known facts that are useful in our algorithms.

For every $\mathrm{\ell }\in \mathrm{𝖡𝗈𝗋𝖽𝖾𝗋𝗌}(S)\cap [k,2k-1]$ the border $S[1..\mathrm{\ell }]$ starts with $S[1..k]$ and implies an occurrence of $S[1..k]$ at position $n-\mathrm{\ell }+1$. Thus, the algorithm starts by finding all the occurrences of $P=S[1..k]$ in $T=S[n-2k+2..n]$, using Lemma 2. If there are no such occurrences, we conclude that $\mathrm{𝖡𝗈𝗋𝖽𝖾𝗋𝗌}(S)\cap [k,2k-1]$ is empty. Otherwise, we distinguish between two cases. If there is a single occurrence of $P$ in $T$, the algorithm is trying to extend this occurrence to a border. Namely, if $S[1..k]=S[n-\mathrm{\ell }+1..n-\mathrm{\ell }+k]$, the algorithm checks whether $S[1..\mathrm{\ell }]=S[n-\mathrm{\ell }+1..n]$ by straightforward characters comparisons. Notice that since in this case there is a single occurrence, the time required for all those comparisons is $O(k)$. In this case, the algorithm outputs ${\mathrm{\ell }}_{\min }=\mathrm{\ell }$, $p=1$ and $m=1$ if it discovers that $S[1..\mathrm{\ell }]$ is a border, or returns $\mathrm{𝗇𝗎𝗅𝗅}$ otherwise.

In case where there are multiple occurrences of $S[1..k]$, we exploit periodicity as follows. If there are at least two occurrences of $P$ in $T$, all the occurrences form an arithmetic progression. This claim is obvious if there are exactly two occurrences and follows from Fact 3 if there are at least three occurrences. This allows us to represent all the occurrences reported by Lemma 2 in $O(1)$ space (creating the arithmetic progression when the second occurrence is reported and extending the arithmetic progression with every additional occurrence). Denote by $L^{\prime }=\{{\mathrm{\ell }}_{\min }^{\prime }+c\cdot p\mid c\in [0,m-1]\}$ the set of indices $\mathrm{\ell }$ such that $P$ occurs in $n-\mathrm{\ell }+1$. Due to the occurrences of $P$, it must be that the period length of $S[n-{\mathrm{\ell }}_{\min }^{\prime }-(m-1)\cdot p+1..S-{\mathrm{\ell }}_{\min }^{\prime }+k]$ is exactly $p$. The algorithm finds where this period breaks both in the prefix and in the suffix, as follows. In the prefix, let $v_1\in [k+1,2k-1]$ be the smallest index where $S[v_1]\ne S[v_1-p]$, if such $v_1$ does not exists $v_1=2k+1$. For the suffix, recall that $S[n-{\mathrm{\ell }}_{\min }-(m-1)\cdot p+1..n-{\mathrm{\ell }}_{\min }+k]$ is periodic with period $p$. The algorithm finds the smallest index $v_2>n-{\mathrm{\ell }}_2+k$ such that $S[v_2]\ne S[v_2-p]$, if such an index does not exist, $v_2=-1$.

If $v_2=-1$, then every $\mathrm{\ell }$ such that $S[n-\mathrm{\ell }+1..n-\mathrm{\ell }+k]=P$ is a border of $S$ if and only if . Thus, the set of borders is an arithmetic progression, which can be computed in constant time from $L^{\prime }$ (it is $L^{\prime }\cap [1..v_1-1]$). Notice that in this case, we have indeed that $p$ is the period length of every element except maybe for ${\mathrm{\ell }}_{\min }$. Clearly we also have . Thus, we indeed obtain a generating arithmetic progression.

If $v_2\ne -1$ and $v_1=2k+1$, there are no borders whose length is some $\mathrm{\ell }\in [k,2k-1]$ because for any $\mathrm{\ell }\in [k,2k-1]$ the prefix of length $\mathrm{\ell }$ has period-length $p$, while the suffix of length $\mathrm{\ell }$ does not have period-length $p$.

Finally, if $v_2\ne -1$ this means that $p$ is not a period of $S[n-{\mathrm{\ell }}_{\min }^{\prime }+1..n]$. In this case, if $v_1\ne 2k+1$, we have only one candidate which is $\mathrm{\ell }=v_1+(n-v_2)$. This is because $\mathrm{\ell }$ is only length allowing the position of the first violation of the period $p$ to be both at offset $v_1$ from the beginning and at offset $n-v_2$ from the end of the border.

If $\mathrm{\ell }\ge 2k$ the algorithm concludes that there is no border whose length is in $[k,2k-1]$. Otherwise, the algorithm checks whether $\mathrm{\ell }$ is indeed a border, by performing $\mathrm{\ell }=O(k)$ comparisons. To see why $\mathrm{\ell }$ is the only candidate for a border, notice that $\mathrm{\ell }$ is the only position where the first violation of period $p$ of the prefix and suffix match each other.

The running time of the algorithm is $O(k)$ (both for the pattern matching algorithm of Lemma 2, for verifying $O(1)$ candidates and for finding $v_1$ and $v_2$). The space usage of the algorithm is $O(1)$. $◀$

We are now ready to prove Lemma 9.

To obtain Lemma 9 we consider a partition of the border-lengths into exponential intervals of the form $[2^i,2^{i+1}-1]$. We are using the algorithm of Lemma 10 for every $k$ which is a power of $2$, from $2^0$ to $2^{\lfloor \log n\rfloor }$ to obtain $O(\log n)$ arithmetic progressions. It only remains to prove that the third property of Lemma 9 holds. That is, if ${\mathrm{\ell }}_{\min }^i$ and ${\mathrm{\ell }}_{\min }^j$ are the minimum elements in two different intervals such that then, ${\mathrm{\ell }}_{\min }^i\le \frac{3}{4}{\mathrm{\ell }}_{\min }^j$. If ${\mathrm{\ell }}_{\min }^i\in [k,2k-1]$ and ${\mathrm{\ell }}_{\min }^j\in [k^{\prime },2k^{\prime }-1]$ such that $k^{\prime }>2k$ the claim follows immediately. Thus, we need to prove that the claim holds for two consecutive intervals ${\mathrm{\ell }}_{\min }^i\in [k,2k-1]$ and ${\mathrm{\ell }}_{\min }^j\in [2k,4k-1]$. Let $x={\mathrm{\ell }}_{\min }^i$ and $y={\mathrm{\ell }}_{\min }^j$. Assume to the contrary that $x>\frac{3}{4}y$. Let since $S[1..x]$ is a border of $S[1..y]$ we have that $S[1..y]$ has period $p$. Since $S[1..x]$ is a prefix of $S[1..y]$, $p$ is also a period length of $S[1..x]$ and it holds that . By Fact 7, it must be that $S[1..x-p]=S[1..y-2p]$ is also a cover of $S$. However, since $y\in [2k\mathrm{..4}k-1]$ and we get that $y-2p>y-\frac{y}{2}=\frac{y}{2}$ which implies that $y-2p$ is in $[k,2k-1]$ and is smaller than $x=y-p$. This contradicts $x$ being minimum in $\mathrm{𝖡𝗈𝗋𝖽𝖾𝗋𝗌}(S)\cap [k,2k-1]$. Finally, the time complexity of the algorithm is ${\sum }_{i=1}^{\log n}O(2^i)=O(2^{2\log n})=O(n)$. The algorithm uses $O(1)$ space per each call to Lemma 10 and reuses the space on each call, for a total of $O(1)$ space. Storing the intervals and the arithmetic progression representation of $L_i$’s requires $O(\log n)$ space. $◀$

Recall that $L$ is a generating arithmetic progression, for every ${\mathrm{\ell }}^{\prime }\in L$ we have ${\mathrm{\ell }}^{\prime }\ge p$ and that $p$ is the period length of $S[1..\mathrm{\ell }]$. By Fact 5 it is enough to show that $S[1..{\mathrm{\ell }}^{\prime }]$ covers $S[1..\mathrm{\ell }]$. By definition of arithmetic progression, there exists two non-negative integers such that ${\mathrm{\ell }}^{\prime }={\mathrm{\ell }}_{\min }+m_1\cdot p$ and $\mathrm{\ell }={\mathrm{\ell }}_{\min }+m_2\cdot p$. It is easy to see that for every (where $m$ is the number of elements in the arithmetic progression) $S[1..{\mathrm{\ell }}_{\min }+i\cdot p]$ is a cover of $S[1..{\mathrm{\ell }}_{\min }+(i+1)\cdot p]$. This is because by $p$ being the period of $S[1..{\mathrm{\ell }}_{\min }+(i+1)\cdot p]$, we have that $S[1..{\mathrm{\ell }}_{\min }+i\cdot p]$ is a border of $S[1..{\mathrm{\ell }}_{\min }+(i+1)\cdot p]$ and that ${\mathrm{\ell }}_{\min }+i\cdot p\ge {\mathrm{\ell }}_{\min }/2+p/2+i\cdot p\ge ({\mathrm{\ell }}_{\min }+(i+1)p)/2$. Therefore, every index of $S[1..{\mathrm{\ell }}_{\min }+(i+1)\cdot p]$ is covered either by the prefix, or by the suffix occurrence of $S[1..{\mathrm{\ell }}_{\min }+i\cdot p]$. Thus, by a simple induction we get that $S[1..{\mathrm{\ell }}^{\prime }]$ covers $S[1..\mathrm{\ell }]$, as required. $◀$

The following corollary follows immediately from Lemma 11.

Thus, to find all the cover-lengths in a given arithmetic progression, the algorithm first verifies whether $S[1..{\mathrm{\ell }}_{\min }]$ covers $S$, which implies whether or not $L^{cover}\ne \mathrm{\varnothing }$. In the following simple lemma, we show that such a verification can be done in $O(n)$ time using $O(1)$ working space.

The algorithm uses $\mathrm{𝖯𝖬}$ - the pattern matching algorithm of Lemma 2 with $S$ as the text and $P=S[1..\mathrm{\ell }]$ as the pattern. Recall, that this algorithm is a real-time algorithm that outputs all the occurrences of $P$ in $S$ from left to right. At any moment, the algorithm maintains the position of the last occurrence. If at some point there are $|P|$ consecutive characters without any occurrence of $P$ or if $P$ is not a suffix of $S$, the algorithm halts and reports that $S[1..\mathrm{\ell }]$ does not cover $S$. Otherwise, the algorithm reports $S[1..\mathrm{\ell }]$ is a cover of $S$. The complexities of the algorithm are dominated by the algorithm of Lemma 2, and are as stated. The correctness of the algorithm follows from the definition of a cover. $◀$

In case $S[1..{\mathrm{\ell }}_{\min }]$ is indeed a cover of $S$, it remains to find $m_c$ - the number of elements in $L^{cover}=L\cap \mathrm{𝖢𝗈𝗏𝖾𝗋𝗌}(S)$, the arithmetic progression of covers (see Corollary 12). In the following lemma, we show how to do it in $O(n)$ time and $O(1)$ working space.

The algorithm first determines whether $S[1..{\mathrm{\ell }}_{\min }]$ and $P=S[1..{\mathrm{\ell }}_{\min }+p]$ cover $S$, using Lemma 13. If one of them does not cover $S$, the answer is simple by Corollary 12 (it is $m_c=0$ if $S[1..{\mathrm{\ell }}_{\min }]$ is not a cover and $m_c=1$ if it is a cover and $P$ is not a cover). The algorithm finds all occurrences of $P$ in $S$ one after the other. The algorithm partitions the occurrences into maximal (non-overlapping) arithmetic progressions with a difference of exactly $p$, and maintains the shortest maximal arithmetic progression of occurrences. Let $minOccs$ denote the number of occurrences in the shortest arithmetic progression. Then, the algorithm returns $\min \{minOccs+1,m\}$ as $m_c$. See Algorithm 1.

Since $\mathrm{𝖯𝖬}$ uses $O(1)$ space and takes $O(1)$ time per character, the algorithm uses $O(1)$ working space and runs in $O(n)$ time.

If $S[1..{\mathrm{\ell }}_{\min }]$ is not a cover of $S$, clearly, $m_c=0$, and the algorithm reports the correct answer. Similarly, if $S[1..{\mathrm{\ell }}_{\min }]$ is a cover and $S[1..{\mathrm{\ell }}_{\min }+p]$ is not a cover then by Lemma 11 $m_c=1$ and the algorithm reports the right value.

Let us consider the case where $S[1..{\mathrm{\ell }}_{\min }+p]$ is a cover of $S$. Let $m^{\prime }=\min (minOccs+1,m)$ and let ${\mathrm{\ell }}^{\prime }={\mathrm{\ell }}_{\min }+(m^{\prime }-1)\cdot p$. We have to prove that $m_c=m^{\prime }$. Let ${\mathrm{\ell }}^{\ast }={\mathrm{\ell }}_{\min }+(m_c-1)\cdot p$ be the maximum element in $L$ such that $S[1..{\mathrm{\ell }}^{\ast }]$ covers $S$.

Since $L$ is a generating arithmetic progression, the period of $P=S[1,{\mathrm{\ell }}_{\min }+p]$ is $p$. Therefore, due to Fact 4, when the algorithm find that the next occurrence is not at difference $p$ from the previous one, it is at difference strictly more than $p$. Algorithm 1 essentially iterates these arithmetic progressions, and keeps track on the shortest arithmetic progression encountered throughout the iteration as $minOccs$. It follows that there is an index $i^{\prime }$ such that:

1. 1.

   For every $t\in [0..minOccs-1]$ there is an occurrence of $P$ at index $i^{\prime }+p\cdot t$.

2. 2.

   Both $i^{\prime }-p$ and $i^{\prime }+p\cdot (minOccs)$ are not occurrences of $P$.

We start by showing that $minOccs+1\ge m_c$. Assume to the contrary that . Since $S[1..{\mathrm{\ell }}^{\ast }]$ is a cover, it must hold that an occurrence of $S[1..{\mathrm{\ell }}^{\ast }]$ covers the index $i^{\prime }+p-1$, say at index $j^{\prime }$. Since $j^{\prime }$ is in particular an occurrence of $P$, and $i^{\prime }$ is also an occurrence of $P$, Fact 4 implies that either $j^{\prime }=i^{\prime }$ or $j^{\prime }\notin [i^{\prime }-p+1..i^{\prime }+p-1]$. If $j^{\prime }\le i^{\prime }-p$, then, we have that $S[i^{\prime }-p..i^{\prime }+p-1]$ has period $p$, which together with the fact that $S[i^{\prime }..i^{\prime }+|P|-1]$ has period $p$ implies that $S[i^{\prime }-p..i^{\prime }+|P|-p-1]=S[i^{\prime }..i^{\prime }+|P|-1]$, a contradiction to $i^{\prime }-p$ not being an occurrence of $P$. If $i^{\prime }=j^{\prime }$, we have that there are $m_c-1>minOccs$ consecutive occurrences of $P$ following $i^{\prime }$, a contradiction to $i^{\prime }+minOccs\cdot p$ not being an occurrence of $P$.

We proceed to show that $S[1..{\mathrm{\ell }}^{\prime }]$ is a cover of $S$, which implies that $m^{\prime }\le m_c$. Let $i\in [n]$ be an index. Since $P$ is a cover of $S$, $i$ is covered by some occurrence of $P$ at index $j$. Let $c^{\prime }$ be the value of $current$ after Algorithm 1 iterated the occurrence $j$. By the definition of $current$, we know that there is an occurrence of $P$ at index $j-p\cdot t$ for every $t\in [0..c^{\prime }-1]$. We also know that throughout the following $m^{\prime }-1-c^{\prime }$ iterations of the algorithm, the value of $current$ will increase to at least $m^{\prime }-1$ before being reset to $1$. Therefore, there are occurrences of $P$ in $j+p\cdot c^{\prime }$ for every $p\in [0,m^{\prime }-1-c^{\prime }]$ as well. In conclusion, for $j^{\prime }=j-(c^{\prime }-1)\cdot p$, there are occurrences of $P$ in $j^{\prime }+p\cdot t$ for every $t\in [0,m^{\prime }-1]$ which means that there is an occurrence of $S[1..{\mathrm{\ell }}^{\prime }]$ at index $j^{\prime }$ containing all of these occurrences. In particular, this occurrence of $S[1..{\mathrm{\ell }}^{\prime }]$ covers the occurrence of $P$ that covers $i$, which means that $S[1..{\mathrm{\ell }}^{\prime }]$ covers $i$. $◀$

To conclude this section, one can use Lemmas 9 and 14 to output all covers of $S$ in $O(n\log n)$ time and $O(\log n)$ space, by first obtaining the arithmetic progressions from Lemma 9 and then apply Lemma 14 on each one of them. In Section 5 we will show how to reduce the running time of finding all covers to $O(n)$ while preserving $O(\log n)$ working space.

Let $L_1,L_2,\mathrm{\dots },L_t$ be the arithmetic progressions that Lemma 9 outputs. Their union forms $\mathrm{𝖡𝗈𝗋𝖽𝖾𝗋𝗌}(S)$, ordered by increasing value of first element. Let ${\mathrm{\ell }}_1,{\mathrm{\ell }}_2,\mathrm{\dots },{\mathrm{\ell }}_t$ be the sequence of elements, such that ${\mathrm{\ell }}_i$ is the first element in $L_i$. In addition, let ${\mathrm{\ell }}_{t+1}=n$ be the length of $S$. Recall that by Lemma 9 we have for every and that $t=O(\log n)$. We denote $F=F_S=({\mathrm{\ell }}_1,{\mathrm{\ell }}_2,\mathrm{\dots },{\mathrm{\ell }}_{t+1})$.

We introduce a recursive algorithm that finds for a given $i$ the largest such that $S[1..{\mathrm{\ell }}_j]$ is a cover of $S[1..{\mathrm{\ell }}_i]$. In particular, when applying the algorithm with $i=t+1$ the output is the largest $j$ such that $S[1..{\mathrm{\ell }}_j]$ covers $S[1..{\mathrm{\ell }}_{t+1}]=S[1..n]=S$. Later in Section 5.1 we will use this lemma to find $F\cap \mathrm{𝖢𝗈𝗏𝖾𝗋𝗌}(S)$ and report all covers-lengths of $S$.

(See Algorithm 2.) We first consider the base case, where $i=1$, in this case there is no value , and the algorithm returns $\mathrm{𝗇𝗎𝗅𝗅}$.

Now, we consider the general case where $i>1$. The algorithm runs in iterations, checking a candidate $j$ in each iteration (starting from $j=i-1$) to determine whether $S[1..{\mathrm{\ell }}_j]$ covers $S[1..{\mathrm{\ell }}_i]$. At the end of each iteration, the algorithm either finds that $S[1..{\mathrm{\ell }}_j]$ indeed covers $S[1..{\mathrm{\ell }}_i]$, or identifies the largest prefix $S[1..x]$ of $S[1..{\mathrm{\ell }}_i]$ that is covered by $S[1..{\mathrm{\ell }}_j]$. The next candidate is the largest such that $S[1..{\mathrm{\ell }}_{j^{\prime }}]$ covers $S[1..{\mathrm{\ell }}_j]$, which is retrieved via a recursive call. In the next iteration, the algorithm does not need to verify that $S[1..{\mathrm{\ell }}_{j^{\prime }}]$ covers $S[1..x]$, since it follows from the fact that $S[1..{\mathrm{\ell }}_{j^{\prime }}]$ covers $S[1..{\mathrm{\ell }}_j]$ and $S[1..{\mathrm{\ell }}_j]$ covers $S[1..x]$ by Fact 5. Thus, the algorithm proceeds to the next iteration, starting to verify that $S[1..{\mathrm{\ell }}_{j^{\prime }}]$ covers $S[1..{\mathrm{\ell }}_i]$ from position $x-{\mathrm{\ell }}_{j^{\prime }}+1$. We note that the verification starts at $x-{\mathrm{\ell }}_{j^{\prime }}+1$ and not at position $x+1$, since position $x+1$ can be covered by occurrences of $S[1..{\mathrm{\ell }}_j]$ in the interval $[x-{\mathrm{\ell }}_{j^{\prime }}+2..x+1]$. If the verification fails, we are again in a situation where a maximal prefix covered by $S[1..{\mathrm{\ell }}_{j^{\prime }}]$ was found.

In each iteration, to determine the largest prefix covered by the current candidate $S[1..{\mathrm{\ell }}_j]$, the algorithm employs the $\mathrm{𝖯𝖬}$ algorithm from Lemma 2. We utilize the fact that $\mathrm{𝖯𝖬}$ is a real-time algorithm to halt the algorithm the moment we recognize the largest prefix covered by the current candidate border. This way, the running time of the algorithm is linear in the length of the candidate and the progress we made in covering $S$.

We prove correctness by induction on $i$. The base case $i=1$ follows immediately. Assume that the algorithm is correct for all , and we prove that it is also correct for $i$. We consider the iterations of the while loop (Line 4) and show that at the beginning of each iteration, the following property holds.

We prove the claim by induction on the iterations. At the beginning of the first iteration, $x={\mathrm{\ell }}_j$ implies $S[1..x]=S[1..{\mathrm{\ell }}_j]$ is trivially covered by $S[1..{\mathrm{\ell }}_j]$. Assuming the property holds at the beginning of some iteration, we should prove it holds at the end of the iteration as well. Let $j_{\mathrm{𝖻𝖾𝖿𝗈𝗋𝖾}},x_{\mathrm{𝖻𝖾𝖿𝗈𝗋𝖾}}$ and $j_{\mathrm{𝖺𝖿𝗍𝖾𝗋}},x_{\mathrm{𝖺𝖿𝗍𝖾𝗋}}$ be the values of $j$ and $x$, at the beginning and end of the iteration, respectively. During the iteration, $x_{\mathrm{𝖺𝖿𝗍𝖾𝗋}}$ is set such that $S[x_{\mathrm{𝖻𝖾𝖿𝗈𝗋𝖾}}-{\mathrm{\ell }}_{j_{\mathrm{𝖻𝖾𝖿𝗈𝗋𝖾}}}+1..x_{\mathrm{𝖺𝖿𝗍𝖾𝗋}}]$ is the largest prefix of $S[x_{\mathrm{𝖻𝖾𝖿𝗈𝗋𝖾}}-{\mathrm{\ell }}_{j_{\mathrm{𝖻𝖾𝖿𝗈𝗋𝖾}}}+1..{\mathrm{\ell }}_i]$ covered by $S[1..{\mathrm{\ell }}_{j_{\mathrm{𝖻𝖾𝖿𝗈𝗋𝖾}}}]$. By the induction hypothesis $S[1..{\mathrm{\ell }}_{j_{\mathrm{𝖻𝖾𝖿𝗈𝗋𝖾}}}]$ also covers $S[1..x_{\mathrm{𝖻𝖾𝖿𝗈𝗋𝖾}}]$. Thus, $S[1..x_{\mathrm{𝖺𝖿𝗍𝖾𝗋}}]$ is covered by $S[1..{\mathrm{\ell }}_{j_{\mathrm{𝖻𝖾𝖿𝗈𝗋𝖾}}}]$. Finally $j_{\mathrm{𝖺𝖿𝗍𝖾𝗋}}=\text{max\_}j\text{\_cover}(S,F,j_{\mathrm{𝖻𝖾𝖿𝗈𝗋𝖾}})$, implying (by induction hypothesis regarding the correctness of $\text{max\_}j\text{\_cover}(j)$) that $S[1..j_{\mathrm{𝖺𝖿𝗍𝖾𝗋}}]$ also covers $S[1..x_{\mathrm{𝖺𝖿𝗍𝖾𝗋}}]$, by Fact 5, as required. $\mathrm{⊲}$ Due to Claim 16, at the beginning of each iteration $S[1..{\mathrm{\ell }}_j]$ covers $S[1..x]$. By running the pattern matching algorithm of Lemma 2 from position $x-{\mathrm{\ell }}_j+1$ we guarantee that all occurrences of $S[1..{\mathrm{\ell }}_j]$ that can be used to cover position $x+1$ are found. Thus, at Line 6, the algorithm assigns to $x$ the largest prefix of $S[1..{\mathrm{\ell }}_i]$ that is covered by $S[1..{\mathrm{\ell }}_j]$. In particular, for the value $j$ reported by the algorithm $S[1..{\mathrm{\ell }}_j]$ indeed covers $S[1..{\mathrm{\ell }}_i]$.

On the other hand, let be the largest integer such that $S[1..{\mathrm{\ell }}_{j^{\ast }}]$ covers $S[1..{\mathrm{\ell }}_i]$. By Fact 6, $S[1..{\mathrm{\ell }}_{j^{\ast }}]$ covers all borders $S[1..{\mathrm{\ell }}_i]$ for $i>j$. Therefore, the algorithm at Line 9 never assigns to $j$ values smaller than $j^{\ast }$ (and also not the value $\mathrm{𝗇𝗎𝗅𝗅}$). Thus, the answer returned by the algorithm is never $\mathrm{𝗇𝗎𝗅𝗅}$ and never smaller than $j^{\ast }$.

The space usage of the algorithm in every level of the recursion is clearly $O(1)$. Every recursive call has different integer $i=O(\log n)$. Thus, there are $O(\log n)$ levels of recursion, and the total space usage of the algorithm is $O(\log n)$ space.

We prove by induction that the time complexity is $O({\mathrm{\ell }}_i)$. For $i=1$ the algorithm runs in $O(1)\subseteq O({\mathrm{\ell }}_1)$ time. Let us assume that the running time for every is $O({\mathrm{\ell }}_j)$, and we prove that the running time for $i$ is $O({\mathrm{\ell }}_i)$. Let $j_k$ and $x_k$ be the values of $j$ and $x$, respectively at the beginning of the $k$th iteration (Line 4), and let $x_{k+1}$ be the value of $x_k$ at the end of the $k$th iteration. The runtime of Line 5 is $O((x_{k+1}-x_k+{\mathrm{\ell }}_{j_k})+{\mathrm{\ell }}_{j_k})=O((x_{k+1}-x_k)+{\mathrm{\ell }}_{j_k})$. The runtime of Line 9 is $O({\mathrm{\ell }}_j)$ by the induction hypothesis. All other lines of the loop take $O(1)$ time. Thus, the $k$th iteration costs $O((x_{k+1}-x_k)+{\mathrm{\ell }}_{j_k})$ time. Summing over all iterations, the term $x_{k+1}-x_k$ sums up to $O({\mathrm{\ell }}_i)$ and the sum of ${\mathrm{\ell }}_{j_k}$ is bounded by $O({\sum }_{j=1}^{i-1}{\mathrm{\ell }}_j)=O({\mathrm{\ell }}_i)$, since for every we have ${\mathrm{\ell }}_j\le \frac{3}{4}{\mathrm{\ell }}_{j+1}$. Thus, the algorithm runs in $O({\mathrm{\ell }}_i)$ time, as required. $◀$

Let $𝒜={[1..\sqrt{n}]}^{\frac{\log n}{10}}$ be set of arrays of size $t=\frac{\log n}{10}$ with each entry being a number in $[1..\sqrt{n}]$. Clearly, $\log |𝒜|=\mathrm{\Theta }({\log }^{2}n)$. We prove the statement by showing an injection from $𝒜$ to $C_n$.

Let $A=(a_1,a_2,\mathrm{\dots }{a}_t)\in 𝒜$. We construct a string $S_A$ corresponding to $A$ as follows. $S_0=a^{\sqrt{n}}b{a}^{\sqrt{n}}$. For every $i\in [1..t]$ we define $S_i=S_{i-1}\cdot S_{i-1}[a_i..|S_{i-1}|]$. Finally, we define $S_A=S_t$.

By the construction for every $i\in [1..t]$ we have $|S_i|\le 2|S_{i-1}|$. Since $|S_0|=2\sqrt{n}+1$ and $t=\frac{\log n}{10}$ we get by simple induction that $|S_A|=|S_t|\le 2^{\frac{\log n}{10}}|S_0|\le n^{\frac{1}{10}}\sqrt{n}\le n$.

Notice that for every $i\in [0..t]$, the string $S_i$ starts and ends with $a^{\sqrt{n}}$. It follows that $S_{i-1}$ is both a prefix and a suffix of $S_i$ of length at least $|S_i|/2$. As a consequence, $S_{i-1}$ is a cover of $S_i$. Therefore, by Fact 5 we have that for every $i\in [0,t]$ we have $|S_i|\in \mathrm{𝖢𝗈𝗏𝖾𝗋𝗌}(S)$. We next show how to recover all lengths of $|S_i|$s from $\mathrm{𝖢𝗈𝗏𝖾𝗋𝗌}(S)$.