`NAIVE-STRING-MATCHER(T,P)`

1.

2.

3. for to

4. if

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,

.

Recall that,

.

Then,

Thus, the expected number of total comparisons is optimal for uniform random input,

**Q.E.D.**

Advertisements