A6 1d) Hint
Michael Soltys

For question 1d) on assignment 6, consider the following (alternative)
pattern matching algorithm: let x,y be strings over {0,1}, |x|=n,
|y|=m, and n is not bigger than m.  We want to know if x is a
substring of y.

Let y(i)=y_i...y_{i+n-1}, and let a be the decimal representation of x
(i.e., a=x_12^{n-1}+...+x_n), and a(i) the decimal representation of
y(i).

Clearly, there is a match iff there exists an i in {1,...,m-n+1} such
that a=a(i).

Finally, let p be a randomly chosen prime in {1,...,nm^2}, and
consider the computation of a and a(i) modulo p.  Then (a(i+1) mod p)
can be obtained easily from (a(i) mod p).

Now run the algorithm as follows: if for some i, (a mod p) and (a(i)
mod p) are equal, then test if x and y(i) match (bit by bit).  If a
match is found, stop.  Otherwise choose a new random prime p in
{1,...,nm^2} and re-initialize the search at position (i+1).

Translate this idea for use in 1d).  Of course, you can ignore the
problem of "choosing a random prime"; just assume that it can be done.