We are given two strings $S=a_1 a_2 \dots a_L$ and $T=b_1 b_2 \dots b_l$ on some alphabet.

The string $S$ is cut into substrings, such that for each $a_i$ in $S$, there's a probability $p_i$ that a cut is made after $a_i$. For example, $S$ may be cut into the substrings:

$$S_1 = a_1 a_2a_3, \hspace{5 mm} S_2 = a_4 a_5, \hspace{5 mm} S_3 = a_6 a_7...a_L $$

which means that $S$ was cut after $a_3$ and after $a_5$. The probability of this is


After cutting $S$, what's the expected count of occurrences of $T$ in the resulting substrings?

I need an algorithm that computes this expected count.

More precisely, the input is the strings $S$ and $T$, and the probabilities $p_i$ for each character in $S$. The output is the expected number of occurrences of $T$ in the resulting substrings of $S$. Is there an efficient algorithm for this problem?

  • 2
    $\begingroup$ Sure. Just find all occurrences of T in S, calculate the survival probability for each occurrence (just multiply the corresponding $(1-p_i)$) and add them up. You also seem to be a bit confused because the probability of the cut you posted as an example is not $p_3p_5$ but rather $(1-p_1)(1-p_2)p_3(1-p_4)p_5(1-p_6)\dots(1-p_{L-1})$. $\endgroup$
    – fedja
    Feb 16, 2013 at 3:47
  • $\begingroup$ @fedja I fixed the mistake in the probability of my example. But I think the solution is not that simple. Are you sure your solution still applies if different occurrences of $T$ in $S$ overlap? $\endgroup$
    – a06e
    Feb 16, 2013 at 4:01
  • $\begingroup$ Certainly. You see, the expectation is additive no matter what. Of course, we count all occurrences of T in all pieces here. $\endgroup$
    – fedja
    Feb 16, 2013 at 4:05

1 Answer 1


Fedja's comment is correct; see linearity of expectation (which doesn't require independence).


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .