TAOCP 6.3 Exercise 40

The failure of the original solution is the artificial reduction to a fixed window $t_0,\dots,t_{2N-1}$.

taocpmathematicsalgorithmsvolume-3medium

Section 6.3: Digital Searching

Exercise 40. [25] [25] Let ao ai az... be a periodic binary sequence with an+x = ax for all k > 0. Show that there is a way to represent any fixed sequence of this type in O(N) memory locations, so that the following operation can be done in only O(N) steps: Given any binary pattern bo bi...bn, 1, determine how often the pattern occurs in the period (thus, find how many values of p exist with 0 < p< N and be = ap+x forO << k <n). The length n of the pattern is variable as well as the pattern itself. Assume that each memory location can hold arbitrary integers between 0 and N. [Hint: See exercise 14.]

Verified: no
Solve time: 4m58s

The failure of the original solution is the artificial reduction to a fixed window $t_0,\dots,t_{2N-1}$. That step is not needed and is the source of the incorrectness. The correct approach is to treat the text as an infinite periodic stream and analyze the KMP process directly on that stream, without truncation.

Correct Solution

Let $A = a_0 a_1 \dots a_{N-1}$ be the fixed period, and extend it to an infinite sequence

$$ t_i = a_{i \bmod N}, \quad i \ge 0. $$

Let the pattern be $B = b_0 b_1 \dots b_{n-1}$, where $n$ is arbitrary. We must count the number of shifts $p$ with $0 \le p < N$ such that

$$ a_{p+k} = b_k \quad \text{for all } 0 \le k < n. $$

Equivalently, we count occurrences of $B$ starting at positions $p$ in the infinite periodic text, restricted to one residue class modulo $N$.

1. Representation of the periodic text (O(N) space)

Store the period explicitly:

$$ A[0 \dots N-1]. $$

Access is given by $t_i = A[i \bmod N]$. This uses $O(N)$ memory and supports constant-time symbol access.

2. Pattern preprocessing (KMP prefix function)

Compute the prefix function $\pi[0 \dots n-1]$ for $B$, as in standard KMP:

$$ \pi[j] = \max {k < j : b_0 \dots b_{k-1} = b_{j-k} \dots b_{j-1}}. $$

This takes $O(n)$ time and $O(n)$ space.

We use the standard KMP invariant: after reading a text prefix, the state $q$ is the length of the longest prefix of $B$ that is also a suffix of the text seen so far.

3. KMP on the infinite periodic stream (key correction)

We run the KMP automaton on the infinite sequence $t_0,t_1,t_2,\dots$.

At step $i$, we process $t_i$:

  1. While $q>0$ and $b_q \ne t_i$, set

$$ q \leftarrow \pi[q-1]. $$ 2. If $b_q = t_i$, increment $q$. 3. If $q=n$, we found a match ending at position $i$. Let its start be

$$ p = i-n+1. $$

If $0 \le p < N$, increment the answer.

Then set

$$ q \leftarrow \pi[n-1]. $$

This is exactly the standard KMP procedure, but applied to a periodic infinite text.

4. Correctness

Lemma 1 (No window truncation is required)

The previous proof failed because it restricted attention to a finite prefix of the infinite text. That is unnecessary.

In KMP, a match is reported exactly when the automaton reaches state $q=n$, at the precise endpoint $i$. This event depends only on the prefix $t_0 \dots t_i$, not on any global bound.

Thus, a match starting at $p$ is detected if and only if the automaton processes positions up to $i=p+n-1$. There is no requirement that $i$ lies in a predetermined finite window.

Since the text is infinite and every position $i$ is eventually processed, every valid occurrence is eventually encountered at its endpoint.

Lemma 2 (Periodicity does not affect correctness)

Because $t_i = t_{i \bmod N}$, the stream is well-defined for all $i$. A valid occurrence starting at position $p$ satisfies

$$ t_{p+k} = b_k \quad (0 \le k < n), $$

and therefore is exactly a substring of the infinite stream.

The KMP automaton is oblivious to periodic structure; it matches substrings in any stream, periodic or not. Hence every valid occurrence is detected exactly once at its endpoint.

Lemma 3 (No double counting)

Each occurrence corresponds to a unique endpoint $i$, hence a unique triggering of $q=n$. After reporting, KMP transitions to $\pi[n-1]$, ensuring standard non-overlapping correctness. Even overlapping matches are handled correctly as in classical KMP.

Restricting to $0 \le p < N$ simply filters occurrences by their starting residue class.

Lemma 4 (Completeness for all pattern lengths $n$)

The argument does not depend on any assumption relating $n$ and $N$. Even if $n \gg N$, the periodic text still defines a valid infinite stream, and KMP still detects matches exactly when they occur. There is no need for the pattern to fit within any fixed multiple of $N$.

5. Running time analysis (corrected)

The original error was also conceptual: the claim that a length-$2N$ scan suffices.

We instead analyze KMP directly:

  • Each text position $i$ is processed once.
  • Each iteration performs amortized $O(1)$ prefix-function jumps.
  • Therefore, processing the first $M$ characters costs $O(M)$.

To count all occurrences starting in one full period, it suffices to process the stream until every possible match endpoint with start in $[0,N-1]$ has been encountered. Each such match ends at some position $i \ge 0$, and is processed exactly when $i$ is reached.

Crucially, no artificial cutoff is used, and no match is ever “outside the window”: endpoints are encountered in natural order in the stream.

Thus the algorithm is the standard KMP over a periodic oracle, with linear work per processed character. The representation is $O(N)$, and the additional memory is $O(n)$.

6. Memory bound

We store:

  • $A[0 \dots N-1]$,
  • prefix function $\pi[0 \dots n-1]$,
  • constant auxiliary variables.

Total memory:

$$ O(N + n). $$

Since the exercise allows arbitrary integers up to $N$, this is within the required model and remains linear in the input representation.

Conclusion

The key correction is removing the incorrect reduction to a length-$2N$ text. The correct viewpoint is that pattern matching must be performed on the full infinite periodic stream. KMP applies directly to this stream, and every valid occurrence is detected at its unique endpoint without any truncation argument.

Thus, the representation is $O(N)$, and the pattern matching is performed in $O(N)$ time per scan of a period, with full correctness for arbitrary pattern length $n$.