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:



next move:



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!

  • $\begingroup$ You can get displayed equations by using double dollar signs instead of single dollar signs. $\endgroup$
    – joriki
    Jun 18 '16 at 17:17
  • $\begingroup$ See also math.stackexchange.com/questions/1597913. $\endgroup$
    – joriki
    Jun 18 '16 at 17:39
  • $\begingroup$ 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. $\endgroup$
    – joriki
    Jun 18 '16 at 17:45

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)\;. $$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.