TAOCP 7.1.4 Exercise 66
Let $S=s_0s_1\ldots s_{n-1}$ be the given $n$-bit string.
Section 7.1.4: Binary Decision Diagrams
Exercise 66. [20] [20] Complete Algorithm S by explaining what to do in step S1 if f ◦g turns out to be trivially constant.
Verified: no
Solve time: 9m48s
Solution
Let $S=s_0s_1\ldots s_{n-1}$ be the given $n$-bit string. The de Bruijn cycle property of $(f_n(0)f_n(1)\ldots f_n(2^n-1))$ implies that there exists a unique index $k$ modulo $2^n$ such that the length-$n$ window starting at $k$ equals $S$, that is
$$ (f_n(k),f_n(k+1),\ldots,f_n(k+n-1)) = S. $$
The construction of $f_n$ in Exercises 97–98 is recursive in powers of two. For even $n=2m$, Exercise 97(d) gives the structural decomposition
$$ f_{2m}(2k) = f_m(k), \qquad f_{2m}(2k+1) = 1 + f_m(k+\delta_m)\pmod 2. $$
This separates even and odd positions of the cycle into two interleaved transforms of the length-$2^m$ cycle.
For a window of length $2m$ starting at position $2k$, the even-indexed bits of the window are
$$ f_{2m}(2k+2i)=f_m(k+i), $$
and the odd-indexed bits are
$$ f_{2m}(2k+2i+1)=1+f_m(k+i+\delta_m)\pmod 2. $$
Hence the even subsequence of the window is a length-$m$ window of $f_m$, and the odd subsequence is the bitwise complement of a $\delta_m$-shifted length-$m$ window of $f_m$.
Define the projections of $S$ by
$$ S^{(0)} = s_0s_2\cdots s_{2m-2}, \qquad S^{(1)} = s_1s_3\cdots s_{2m-1}. $$
A necessary and sufficient condition for the occurrence of $S$ starting at $2k$ is that
$$ (f_m(k),f_m(k+1),\ldots,f_m(k+m-1)) = S^{(0)} $$
and simultaneously
$$ (f_m(k+\delta_m),f_m(k+1+\delta_m),\ldots,f_m(k+m-1+\delta_m)) = \overline{S^{(1)}}, $$
where $\overline{\cdot}$ denotes bitwise complement.
The first condition determines a unique candidate $k_0$ modulo $2^m$, since by Exercise 7.2.1.1.98 one can locate any length-$m$ string in the cycle of $f_m$ in deterministic time. The second condition is a consistency check that determines whether the occurrence at $k_0$ extends to a valid occurrence at even position.
This yields the even-start candidate $k=2k_0$ if and only if both conditions hold.
For odd starting positions $2k+1$, the same argument applies after swapping the roles of the two interleaved subsequences. The window satisfies
$$ f_{2m}(2k+1+2i)=1+f_m(k+i+\delta_m), $$
and
$$ f_{2m}(2k+1+2i+1)=f_m(k+i+1). $$
Thus $S$ must satisfy the analogous pair of constraints with the roles of $S^{(0)}$ and $S^{(1)}$ exchanged and with the corresponding shift alignment. This again reduces to a single location problem in the cycle of $f_m$, producing a candidate $k_1$ and giving the odd-start position $k=2k_1+1$ when consistent.
The resulting algorithm proceeds recursively. For $n=2$, the cycle is explicitly known from Exercise 97(a), so the position of any 2-bit string is obtained by direct lookup in ${00,01,11,10}$.
For $n>2$, write $n=2m$. Compute the two projected strings $S^{(0)}$ and $S^{(1)}$. Use the algorithm of Exercise 7.2.1.1.98 to locate $S^{(0)}$ in the cycle of $f_m$, producing $k_0$. Verify whether the shifted complement condition holds; if it does, record $k=2k_0$.
Then repeat the same procedure with roles reversed to obtain $k_1$ for the odd-start case; if consistent, record $k=2k_1+1$.
Exactly one of these two candidates is valid, since the de Bruijn property guarantees a unique occurrence of $S$.
The recursion depth is the number of times $n$ can be divided by $2$ until reaching $2$, and each level performs a constant number of calls to the location procedure for $f_m$ together with linear-time projection and verification on $n$ bits. This yields an overall efficient algorithm for locating $S$ in the cycle.
This completes the construction of the required locating algorithm. ∎