expected number of comparisons of naive string matching

Question

from CLRS 32.1-3:

Suppose that pattern $P$ and text $T$ are randomly chosen strings of length $m$ and $n$, respectively, from the $d$-ary alphabet $\sum_d > \{0,1,...,d-1\}$, where $d \ge 2$. Show that the expected number of character-to-character comparisons made by the implicit loop in the naive string-matching algorithm is

$(n-m+1) \frac{1-d^{-m}}{1-d^{-1}} \le 2(n-m+1)$

over all executions of this loop. (Assume that the naive algorithm stops comparing character for a given shift once it finds a mismatch of matches the entire pattern.)

So far this is what I've got:

For the naive searching algorithm, the matching will look like this:

$T_1-T_2-T_3-...-T_m-T_{m+1}-...-T_{n-1}-T_n$

$P_1-P_2-P_3-...-P_m$

next move:

$T_1-T_2-T_3-...-T_m-T_{m+1}-...-T_{n-1}-T_n$

$\hspace{1cm}P_1-P_2-...-P_m$

Thus, there will be a total of $(n-m+1)$ moves (trivial).

This is where I become less sure of my reasoning:

The average number of matches will be the sum of the probabilities of matching $j$ characters times $j$ for $j$ from $1$ to $m$, i.e. $j * P_{j\_characters\_match}$ where $P_{j\_characters\_match}$ is the probability that the first j characters match between the test string and the text.

So $P_{1\_character\_matches}$ (the probability of not matching the first character) = $1-\frac{1}{d}$

$P_{2\_character\_matches}$ (the probability of matching the first character and not the second character is) = $\frac{1}{d} \left(1-\frac{1}{d}\right)$

$P_{3\_character\_matches}$ (the probability of matching the first character and the second character, but not the third character is) = $\frac{1}{d^2} \left(1-\frac{1}{d}\right)$

etc. etc. etc.

So, by my reasoning, the average number of matches will be:

$(n-m+1)\left(1-\frac{1}{d}\right)\sum\limits_{i=1}^m \frac{i}{d^{i-1}}$

however, I'm lost at how to reduce the summation on the right in order to get the correct value given in the problem. I tried looking around, and even putting the summation into wolfram alpha, but nothing seems to give me what I need.

As always, any help would be great!

You can get displayed equations by using double dollar signs instead of single dollar signs. — joriki, Jun 18 '16 at 17:17
In case you do ever need to sum a geometric series times a polynomial, see e.g. this answer for a technique to do that. — joriki, Jun 18 '16 at 17:45

score 0 · Answer 1 · answered Jun 18 '16 at 17:36

Your count is a bit off, since you only need to compare $m$ characters even if the $m$-th one matches. We could add a correction for that, but in any case a more efficient way to count is by adding up the probabilities for the individual characters to be compared:

\begin{align} (n-m+1)\sum_{i=0}^{m-1}d^{-i}=(n-m+1)\frac{1-d^{-m}}{1-d^{-1}}\;. \end{align}

This is a useful approach in many circumstances; for a random variable $X$ that takes non-negative integer values,

$$ E[X]=\sum_{x=0}^\infty\textsf{Pr}(X\gt x)\;. $$

expected number of comparisons of naive string matching

1 Answers1