% !TEX root = kFKM.tex

%This section revisits Martin's Greedy algorithm to construct universal cycles, which we have mentioned in Section~\ref{sec:intro}. 
%In this section, we provide a greedy interpretation of the FKM algorithm for $\mathbf{S}$ when $\mathbf{S} \in \CLASS{n}{k}$. 
%Recall the Greedy algorithm we mention in Section~\ref{sec:intro} which starts with the sequence $k^{n-1}$, and extends according to the simple rule below:
%
%\begin{quote}
%\emph{Repeatedly append the smallest symbol in $\{1, 2, \ldots, k\}$ so that substrings of length $n$ in the resulting sequence are distinct and in $\mathbf{S}$.}
%\end{quote}
%
%\noindent

In this section we prove the greedy portion of Theorem \ref{thm:main} and Corollary \ref{cor:kn}, and that the generated universal cycles are all lexicographically smallest.

Let $\GREEDY{\mathbf{S}}$ denote the sequence generated by the greedy algorithm after removing the initial $k^{n-1}$.
%In this section, we prove that $\GREEDY{\mathbf{S}} = \FKM{\mathbf{S}}$ when ${\mathbf{S}} \in \CLASS{n}{k}$. 
%Let $m = |\mathbf{N}(\mathbf{S})|$, and $\alpha_1, \alpha_2, \ldots, \alpha_m$ be the necklaces in $\mathbf{S}$ listed in lexicographic order.
We need to prove that $\GREEDY{\mathbf{S}} = \FKM{\mathbf{S}}$ and this is the lexicographically smallest universal cycle when $\mathbf{S} \in \CLASS{n}{k}$.
%\begin{equation*}
%\GREEDY{\mathbf{S}} = \FKM{\mathbf{S}} = \aprefix{\alpha_1} \cdot \aprefix{\alpha_2} \cdots \aprefix{\alpha_m}.
%\end{equation*}
%We further prove that both $\GREEDY{\mathbf{S}}$ and $\FKM{\mathbf{S}}$ produce the lexicographically smallest universal cycle for $\mathbf{S}$ when ${\mathbf{S}} \in \CLASS{n}{k}$.
%As a preliminary step of the greedy proof, we prove the following lemma. 
\begin{lemma} \label{cor:k-greedy-prefix}
If $\mathbf{S} \in \CLASS{n}{k}$ and $|\mathbf{S}| > 1$, then the lexicographically smallest necklace in $\mathbf{N}(\mathbf{S})$ is a prefix of $\GREEDY{\mathbf{S}}$. 
\end{lemma}
\begin{proof}
By contradiction. 
Let $\alpha = a_1 a_2 \cdots a_n$ be the lexicographically smallest necklace in $\mathbf{N}(\mathbf{S})$. 
The string $\alpha$ is also the lexicographically smallest string in $\mathbf{S}$ since $\mathbf{S}$ is closed under rotation. 
Suppose $\GREEDY{\mathbf{S}}$ starts with prefix $a_1 a_2 \cdots a_i z$ for some $i< n$ and $z \neq a_{i+1}$. 
Observe that $z<a_{i+1}$ by the definition of the greedy algorithm. 
Furthermore, since the greedy algorithm starts with the initial seed $k^{n-1}$, after $i+1$ iterations of the greedy algorithm the length $n$ suffix of the sequence is $\beta = k^{n-i-1} a_1 a_2 \cdots a_i z$. 
Notice that if $\beta \in \mathbf{S}$, then its rotation $a_1 a_2 \cdots a_i z k^{n-i-1}$ must also be in $\mathbf{S}$ since $\mathbf{S}$ is closed under rotation. 
However, $a_1 a_2 \cdots a_i z k^{n-i-1}$ is strictly less than $\alpha$, a contradiction to $\alpha$ being the lexicographically smallest string in $\mathbf{S}$. 
%Observe that a rotation of $\beta$ is $a_1 a_2 \cdots a_i z k^{n-i-1}$ which is strictly less than $\alpha_1$. 
%The string $a_1 a_2 \cdots a_i z k^{n-i-1} \in \mathbf{S}$ since $\mathbf{S}$ is closed under rotation, which leads to a contradiction since $\alpha_1$ is the smallest string in $\mathbf{S}$ by definition. 
%The string $\alpha_1$ is the lexicographically smallest length $n$ string in $\mathbf{S}$ since $\mathbf{S}$ is closed under rotation. 
%Since $\mathbf{S} \in \CLASS{n}{k}$, $k^{n-s} a_1 a_2 \cdots a_s \in \mathbf{S}$ for $1 \leq s \leq n$. 
%By the greedy algorithm, since $k^{n-s} a_1 a_2 \cdots a_s \in \mathbf{S}$ has not appeared before $\alpha_1$, the sequence must extend with $\alpha_1$ after the initial seed $k^{n-1}$. %Thus  $\GREEDY{\mathbf{S}}$ has prefix ${\alpha_1}$ as claimed. 
\end{proof}

\begin{theorem} \label{thm:greedy}
%If $\mathbf{S} \in \CLASS{n}{k}$, then the following greedy algorithm creates a universal cycle for $\mathbf{S}$:

%\begin{itemize}
%\item Start the sequence with $k^{n-1}$;
%\item Repeatedly append the smallest symbol in $\{1, 2, \ldots, k\}$ so that the non-circular substrings of length $n$ in the resulting sequence are distinct and in $\mathbf{S}$;
%\item Remove the $k^{n-1}$ prefix when the above step cannot be repeated.
%\end{itemize}
%$\GREEDY{\mathbf{S}}$ is a universal cycle for $\mathbf{S}$ if $\mathbf{S} \in \CLASS{n}{k}$. 
%Furthermore, the universal cycle equals $\FKM{\mathbf{S}}$.
If $\mathbf{S} \in \CLASS{n}{k}$, then $\GREEDY{\mathbf{S}}$ is equivalent to $\FKM{\mathbf{S}}$.  
\end{theorem}
\begin{proof}
Let $\alpha_1, \alpha_2, \ldots, \alpha_m$ denote the lexicographic ordering of necklaces in $\mathbf{N}(\mathbf{S})$. 
Let $\mathcal{L}_t = \aprefix{\alpha_1}  \aprefix{\alpha_2} \\ \cdots \aprefix{\alpha_{t}}$ for  $1\leq t \leq m$. 
When $m = 1$, $\mathbf{S} = \{k^n\}$ and the greedy algorithm terminates with the correct sequence of length one, namely $\GREEDY{\mathbf{S}} = \FKM{\mathbf{S}} = k$. 
%In the remaining of the proof, we consider $m > 1$.  

For $m > 1$, we prove that $\GREEDY{\mathbf{S}} = \FKM{\mathbf{S}} = \mathcal{L}_m$ by contradiction. 
Suppose $t$ is the smallest value such that $\mathcal{L}_{t+1}$ is not a prefix of $\GREEDY{\mathbf{S}}$, where ${\alpha_t} = a_1 a_2 \cdots a_n = a_1 a_2 \cdots a_{n-j} k^j$ and $a_{n-j} < k$.  
From Lemma~\ref{cor:k-greedy-prefix} we know that $1 \leq t < m$. 
Let $\alpha_{t+1} = b_1 b_2 \cdots b_n$ and $p = |\aprefix{\alpha_{t+1}}|$. 
Let $i$ be the smallest value such that $0< i \leq p$ and $\mathcal{L}_{t}\cdot b_1 b_2 \cdots b_i$ is not a prefix of $\GREEDY{\mathbf{S}}$.  
Let $\beta$ denote the length $n-1$ suffix of $\mathcal{L}_{t}\cdot b_1 b_2 \cdots b_{i-1}$. Such a suffix exists since both $\GREEDY{\mathbf{S}}$ and $\FKM{\mathbf{S}}$ begin with $\alpha_1$ by Lemma~\ref{lem:fkm-prefix} and Lemma~\ref{cor:k-greedy-prefix} when $m>1$. 
There are two cases depending on the value of $i$. 

%By (P2) of Lemma~\ref{cor:properties}, $b_1 b_2 \cdots b_{n-j-1} = a_1 a_2 \cdots a_{n-j-1}$. 
%Thus $\alpha_{t+1} = a_1 a_2 \cdots a_{n-j-1} b_{n-j} b_{n-j+1} \cdots b_n$. 


\begin{description}
\item[Case 1: $0 < i \leq p - j - 1$] By Lemma~\ref{lem:next-necklace-prefix}, $b_1 b_2 \cdots b_{n-j-1} = a_1 a_2 \cdots a_{n-j-1}$. 
Therefore by Lemma~\ref{cor:properties-2}, $\beta = a_{i+1} a_{i+2} \cdots a_n \cdot a_1 a_2 \cdots a_{i-1} $ since $\aprefix{\alpha_{t}}$ is prior to $b_1 b_2 \cdots b_{i-1}$.
%Let $\beta = a_{j+2} a_{j+3} \cdots a_n a_1 a_2 \cdots a_j z$ be the greedy sequence's suffix of length $n$ after adding $z$.
Since $\mathcal{L}_{t}\cdot b_1 b_2 \cdots b_i$ is not a prefix of $\GREEDY{\mathbf{S}}$, the greedy algorithm appends $z$ to $\beta$ where $z < b_i$. 
By Corollary \ref{cor:where}, $\beta z$ is not a rotation of the necklaces $\alpha_1, \alpha_2, \ldots, \alpha_{t-1}$.
However, a rotation of $\beta z$ is equal to $a_1 a_2 \cdots a_{i-1} z a_{i+1} a_{i+2} $ $\cdots a_n$ and is strictly less than $\alpha_{t}$.
Therefore, $\beta z$ is a rotation of some necklace that is between $\alpha_{t-1}$ and $\alpha_{t}$ in lexicographic order, a contradiction to $\alpha_t$ being the necklace after $\alpha_{t-1}$ in the lexicographic ordering of $\mathbf{N}(\mathbf{S})$. 
Thus $z$ must be equal to $b_i = a_i$. 

\item[Case 2: $p-j-1 < i \leq p$] By Lemma~\ref{cor:properties-2}, $\beta = a_{i+1} a_{i+2} \cdots a_{n} b_1 b_2 \cdots b_{i-1}$ which is equal to $a_{i+1} a_{i+2} \cdots \\ a_{n} a_1 a_2 \cdots a_{p-j-1} \cdot b_{p-j} b_{p-j+1} \cdots b_{i-1}$ since $\aprefix{\alpha_{t}}$ is prior to $b_1 b_2 \cdots b_{i-1}$. 
Since $\mathcal{L}_{t}\cdot b_1 b_2 \cdots b_i$ is not a prefix of $\GREEDY{\mathbf{S}}$, the greedy algorithm appends $z$ to $\beta$ where $z < b_i$. 
By Corollary \ref{cor:where}, $\beta z$ is not a rotation of the necklaces $\alpha_1, \alpha_2, \ldots, \alpha_{t}$.
However, a rotation of $\beta z$ is equal to $a_1 a_2 \cdots a_{p-j-1}\cdot b_{p-j} b_{p-j+1} \cdots b_{i-1} z a_{i+1} a_{i+2} \cdots a_{n}$ and is strictly less than $\alpha_{t+1}$.
Therefore, $\beta z$ is a rotation of some necklace that is between $\alpha_{t}$ and $\alpha_{t+1}$ in lexicographic order, a contradiction to $\alpha_{t+1}$ being the necklace after $\alpha_{t}$ in the lexicographic ordering of $\mathbf{N}(\mathbf{S})$. Thus $z$ must be equal to $b_i$. 

\end{description}
%In the first step we prove that the greedy algorithm must extend $\mathcal{L}_t$ by $a_1 a_2 \cdots$ $ a_{p-j-1}$. 
%If this is not the case, then the greedy algorithm extends $\mathcal{L}_t$ by $a_1 a_2 \cdots a_i z$ for some $i < p-j-1$ and $z < a_{i+1}$.
%Let $\beta$ be the length $n$ suffix of the current sequence $\mathcal{L}_t \cdot a_1 a_2 \cdots a_i z$.
%From the proof of Theorem \ref{thm:kFKM}, $\beta = a_{i+2} a_{i+3} \cdots a_n \cdot a_1 a_2 \cdots a_i z$ since $\aprefix{\alpha_{t}}$ is just prior to the suffix $a_1 a_2 \cdots a_i z$.
%By Corollary \ref{cor:where}, $\beta$ is not a rotation of the necklaces $\alpha_1, \alpha_2, \ldots, \alpha_{t}$.
%However, a rotation of $\beta$ is equal to $a_1 a_2 \cdots a_i z a_{i+2} a_{i+3} \cdots a_n$ and is strictly less than $\alpha_{t}$, which contradicts with the definition of $\mathcal{L}_t$. %Thus $G$ must be extended by $a_1 a_2 \cdots a_{|\aprefix{\alpha_{t+1}}|-j-1}$

%In the second step we prove that the greedy algorithm next extends ${\mathcal{L}_t} \cdot a_1 a_2 \cdots $ $a_{p-j-1}$ by $b_{p-j} b_{p-j+1} \cdots b_{p}$.
%If this is not the case, then the greedy algorithm extends the sequence by $b_{p-j} b_{p-j+1} \cdots b_{i} z$ for some $p-j \leq i < p$ and $z < b_{i+1}$.
%Let $\beta$ be the length $n$ suffix of the current sequence $\mathcal{L}_t \cdot a_1 a_2 \cdots a_{p-j-1} \cdot b_{p-j} b_{p-j+1} \cdots b_{i} z$. 
%From the proof of Theorem \ref{thm:kFKM}, $\beta = a_{i+2} a_{i+3} \cdots a_{n} a_1 a_2 \cdots a_{p-j-1} \cdot b_{p-j} b_{p-j+1} \cdots b_{i} z$.
%By Corollary \ref{cor:where}, $\beta$ is not a rotation of the necklaces $\alpha_1, \alpha_2, \ldots, \alpha_{t}$.
%However, a rotation of $\beta$ is equal to $a_1 a_2 \cdots a_{p-j-1}\cdot b_{p-j} b_{p-j+1} \cdots b_{i} z a_{i+2} a_{i+3} \cdots a_{n}$ and is strictly less than $\alpha_{t+1}$.
%Therefore, $\beta$ is a rotation of some necklace that is between $\alpha_{t}$ and $\alpha_{t+1}$ in lexicographic order, which also contradicts with the definition of $\mathcal{L}_t$. 

%Thus, the greedy algorithm must extend $\mathcal{L}_t$ by $a_1 a_2 \cdots a_{p-j-1} b_{p-j} b_{p-j+1} \cdots b_p$, that is $\aprefix{\alpha_{t+1}}$ as claimed.
Thus by proof of contradiction, $\GREEDY{\mathbf{S}} = \FKM{\mathbf{S}} = \mathcal{L}_m$ as claimed. 
\end{proof}

\begin{comment}
Let $\alpha_1, \alpha_2, \ldots, \alpha_m$ be the necklaces in $\mathbf{S}$ listed in lexicographic order. %= L \cap \NECKS{n}{k}$.
When $m=1$, the greedy algorithm terminates with the correct sequence of length one, namely $\FKM{\mathbf{S}} = k$. 
For the remainder of the proof we assume that $m>1$.
We prove that the second step of the greedy algorithm would eventually builds the sequence 
\begin{equation} \label{eq:greedyGrow}
k^{n-1} \cdot \aprefix{\alpha_1} \cdot \aprefix{\alpha_2} \cdots \aprefix{\alpha_i} 
\end{equation}
for each $i = 1,2,\ldots,m$ by induction.
%Note: When $i < m$ we actually prove that the sequence is extended by $\alpha_i$ instead of $\aprefix{\alpha_i}$, and this distinction is justified by (Q3) in the proof of Theorem \ref{thm:kFKM}.

The base case is $i=1$.
Let $\alpha_1 = a_1 a_2 \cdots a_n$.
Since $\alpha_1 \in \mathbf{N}(\mathbf{S})$ and $\mathbf{N}(\mathbf{S})$ is $k$-suffix language, $a_1 a_2 \cdots a_{n-j} k^{j} \in \mathbf{N}(\mathbf{S})$ for all $0 \leq j \leq n$.
Since $\mathbf{S}$ contains the rotations of $\mathbf{N}(\mathbf{S})$, this means that $k^{j} a_1 a_2 \cdots a_{n-j} \in \mathbf{S}$ for all $0 \leq j \leq n$.
We claim that $k^{j} a_1 a_2 \cdots a_{n-j}$ is the lexicographically smallest string in $\mathbf{S}$ with prefix $k^{j}$ for all $0 \leq j \leq n$.
If this is not true, then there would be some string $\beta \in \mathbf{S}$ with a prefix that is strictly less than $a_1 a_2 \cdots a_{n-j}$.
%Therefore, $\beta \in \mathbf{R}$ would be lexicographically smaller than $\alpha_1$.
However, this would imply that there is a necklace in $\mathbf{S}$ that is lexicographically smaller than $\alpha_1$, which is a contradiction.
Therefore, the claim is true.
By taking $j=0, 1,\ldots,n$ the base case is proven.

For the inductive assumption, suppose that \eqref{eq:greedyGrow} is true for $i = t < m$.
When $t = m-1$ we have a special case which is handled at the end of the proof, so in the meantime we assume that $t < m-1$.
We now prove that \eqref{eq:greedyGrow} holds for $i=t+1$.
Let $\alpha_t = a_1 a_2 \cdots a_n$ with suffix $x k^{s}$ for some $x < k$.
Let $\alpha_{t+1} = a_1 a_2 \cdots a_{n-s-1} \cdot b_{n-s} b_{n-s+1} \cdots b_n$ where the stated prefix is justified by the proof of Theorem \ref{thm:kFKM}.
Our proof proceeds in two steps.

In the first step we prove that the greedy algorithm extends its sequence by $a_1 a_2 \cdots a_i$ for all $1 \leq i \leq n-s-1$.
If this is not the case, then the greedy algorithm extends the sequence by $a_1 a_2 \cdots a_i z$ for some $i < n-s-1$ and $z < a_{i+1}$.
Let $\beta$ be the greedy sequence's suffix of length $n$ after adding $z$.
Observe that from the proof of Theorem \ref{thm:kFKM}, $\beta = a_{i+2} a_{i+3} \cdots a_n \cdot a_1 a_2 \cdots a_i z$ since $\alpha_t$ is just prior to the suffix $a_1 a_2 \cdots a_i z$.
%Let $\beta = a_{j+2} a_{j+3} \cdots a_n a_1 a_2 \cdots a_j z$ be the greedy sequence's suffix of length $n$ after adding $z$.
By Corollary \ref{cor:where}, $\beta$ is not a rotation of the necklaces $\alpha_1, \alpha_2, \ldots, \alpha_{t-1}$.
However, a rotation of $\beta$ is equal to $a_1 a_2 \cdots a_i z a_{i+2} a_{i+3} \cdots a_n$ and is strictly less than $\alpha_t$.
Therefore, $\beta$ is a rotation of some necklaces that is between $\alpha_{t-1}$ and $\alpha_{t}$ in lexicographic order.
Thus, $\beta$ is not a rotation of any necklace in $\mathbf{S}$, and hence $\beta \notin \mathbf{S}$.
This is not possible by the definition of the greedy algorithm, and hence the first step has been proven by contradiction.

In the second step we prove that the greedy algorithm next extends its sequence by $b_{n-s} b_{n-s+1} \cdots b_{i}$ for all $n-s \leq i \leq n$.
If this is not the case, then the greedy algorithm extends the sequence by $b_{n-s} b_{n-s+1} \cdots b_{i} z$ for some $n-s \leq i < n$ and $z < b_{i+1}$.
Let $\beta = k^{n-i-1} a_1 a_2 \cdots a_{n-s-1} \cdot b_{n-s} b_{n-s+1} \cdots b_{i} z$ be the length $n$ suffix of the greedy sequence after adding $z$.
By Corollary \ref{cor:where}, $\beta$ is not a rotation of the necklaces $\alpha_1, \alpha_2, \ldots, \alpha_{t}$.
However, a rotation of $\beta$ is equal to $a_1 a_2 \cdots a_{n-s-1}\cdot b_{n-s} b_{n-s+1} \cdots b_{i} z k^{n-i-1} $ and this is strictly less than $\alpha_{t+1}$.
Therefore, $\beta$ is a rotation of some necklaces that is between $\alpha_{t}$ and $\alpha_{t+1}$ in lexicographic order, which is not a rotation of any necklace in $\mathbf{S}$, and hence $\beta \notin \mathbf{S}$.
This is not possible by the definition of the greedy algorithm, and hence the second step has been proven by contradiction. 

To complete the proof we return to the case of $t=m-1$.
From the proof of Theorem \ref{thm:kFKM} we know that $\alpha_{m-1} = x k^{n-1}$ for some $x < k$, and $\alpha_m = k^n$.
Furthermore, the substring $k^n$ does not appear in the sequence created by the greedy algorithm.
Therefore, the greedy algorithm terminates its second step by adding the final symbol $k$.
This completes the induction, and by \eqref{eq:greedyGrow} with $i=m$ we know that the greedy algorithm terminates its third step with the sequence $\FKM{\mathbf{S}}$, which is a universal cycle for $\mathbf{S}$ by Theorem \ref{thm:kFKM}.
\end{comment}


\begin{corollary} \label{cor:smallest}
$\FKM{\mathbf{S}}$ and $\GREEDY{\mathbf{S}}$ produce the lexicographically smallest universal cycle among all universal cycles for $\mathbf{S} \in \CLASS{n}{k}$.
\end{corollary}
\begin{proof}
The greedy algorithm always starts with the lexicographically smallest necklace in $\mathbf{N}(\mathbf{S})$ by Lemma~\ref{cor:k-greedy-prefix}, which is also the lexicographically smallest string in $\mathbf{S}$. 
It then greedily appends the lexicographically smallest possible symbol such that the length $n$ suffix is unique and in $\mathbf{S}$. 
By the definition of the greedy algorithm, appending any smaller symbol results in either a duplicate string, or a string not in $\mathbf{S}$. 
Thus $\GREEDY{\mathbf{S}}$ must be the lexicographically smallest universal cycle.  
%Thus appending any symbol $z$ that is smaller than $x$ from the greedy algorithm leads to a contradiction. 
Also by Theorem~\ref{thm:greedy}, $\FKM{\mathbf{S}}$ and $\GREEDY{\mathbf{S}}$ produce the same universal cycle. 
Therefore, both $\FKM{\mathbf{S}}$ and $\GREEDY{\mathbf{S}}$ produce the lexicographically smallest universal cycle for $\mathbf{S}$. 
\end{proof}

\begin{comment}
The universal cycles for sets in $\CLASS{n}{k}$ created by the greedy algorithm ends wtih $k^n$ as mentioned in Theorem~\ref{thm:greedy}. 
Thus by the same argument of Corollary~\ref{cor:almost-k-suffix}, removal of the last symbol $k$ from the sequence creates a universal cycle for the sets minus $\{k^n\}$. 

\begin{corollary} \label{thm:almost-k-greedy}
%Suppose $L  \subseteq \TUPLES{n}{k}$ is a set with the $k$-suffix property.% and $N = L \cap \NECKS{n}{k}$
If $\mathbf{S} \notin \CLASS{n}{k}$ but $\mathbf{S} \cup \{k^n\} \in \CLASS{n}{k}$, then the following greedy algorithm creates a universal cycle for $\mathbf{S}$:
%Suppose $\mathbf{S} \subseteq \TUPLES{n}{k}$ and $\mathbf{S} \cap \NECKS{n}{k}$ is not $k$-suffix language but $(\mathbf{S} \cup \{k^n\}) \cap \NECKS{n}{k}$ is $k$-suffix language. 
%The following greedy algorithm creates a universal cycle for $\mathbf{S}$:

%N \subseteq \TUPLES{n}{k}$ is a set of necklaces with the $k$-suffix property and $R \subseteq \TUPLES{n}{k}$ is its set of rotations.
\begin{itemize}
\item Start the sequence with $k^{n-1}$;
\item Repeatedly append the smallest symbol in $\{1, 2, \ldots, k\}$ so that the non-circular substrings of length $n$ in the resulting sequence are distinct and in $\mathbf{S}$;
\item Remove the $k^{n-1}$ prefix when the above step cannot be repeated.
\end{itemize}
Furthermore, the universal cycle equals $\FKM{\mathbf{S}}$.
\end{corollary}
\end{comment}

\begin{comment}
\begin{algorithm}[t]                    
\caption{Greedy construction of universal cycles for $\mathbf{S} \subseteq \TUPLES{n}{k}$ which are closed under rotation and $\mathbf{S} \cap \NECKS{n}{k}$ $k$-suffix language.}          
\label{alg:greedy} 
\small
        
\begin{algorithmic} [1]                   
\Procedure{Greedy}{}
%\State $\textrm{Print($0$)}$
\State{$a_1a_2\ldots a_{n-1} \gets k^{n-1}$}
\State{$s \gets n$}
\State $a_s \gets 1$

\Do
	\If{$a_{s-n+1} a_{s-n+2} \ldots a_s \in \mathbf{S}$ \bf{and} $h[a_{s-n+1} a_{s-n+2} \ldots a_s] = 0$}
		\State \Call{Print}{$a_s$}
		\State $h[a_{s-n+1} a_{s-n+2} \ldots a_s] \gets 1$
		\State $s \gets s+1$
		\State $a_s \gets 1$
	\Else
		\State $a_s \gets a_s + 1$
	\EndIf

\doWhile{$a_s \leq k$}
%\State \Call{Print}{$k^{n-1}$}
\EndProcedure
\end{algorithmic}
\end{algorithm}   


Pseudocode of the Greedy algorithm is given in Algorithm~\ref{alg:greedy}. 
The algorithm maintains a hash table to indicate the presence of a length $n$ string that has appeared in the current sequence. 
The algorithm generates $\FKM{\mathbf{S}}$ in $O(n)$ amortized time per bit using $\Omega(|\mathbf{S}|)$ space if the membership tester of $\mathbf{S}$ can be done within $O(n)$ time.
\end{comment}
%

