3. for to
5. then print "pattern occurs at shift "
Ex. from CLRS. The Naïve String matching algorithm is optimal for uniform random text of length and uniform random pattern of length .
Proof. Assume an alphabet of size .
Let be the probability of doing comparisons at line 4.
If then .
Otherwise and .
Then the expected number of comparisons is,
Thus, the expected number of total comparisons is optimal for uniform random input,