Let's first try to solve the task for one word, meaning not for all of its prefixes.

Let's denote with ~S~ the sequence of tones for which we calculate the expected number of key presses in order to hear it. Let ~A~ be the sequence of randomly pressed keys. We denote three types of positions in sequence ~A, p_i^1, p_i^2, p_i^3~.

Each position represents the start of tone sequence ~S~ in sequence ~A~.

1. The general occurrence position of tone sequence ~S~.
2. Each occurrence position of tone sequence ~S~ that is not a part of the suffix of another occurrence of tone sequence ~S~.
3. Each occurrence position of tone sequence ~S~ that starts as a suffix of another type of occurrence.

There are infinitely many of each of these positions in an infinite random sequence ~A~.

Now, let's observe the positions of type 2 and the consecutive position differences. It is not difficult to notice that the average difference between consecutive positions is actually the solution of the problem. More precisely,

$$\displaystyle \lim_{n \to \infty} \frac{(p_{i+1}^2+l-1)-(p_i^2+l-1)}{n} = \lim_{n \to \infty} \frac{p_{i+1}^2-p_i^2}{n}$$

is the solution to the problem. Let's denote with ~F(1), F(2), F(3)~ the frequencies of appearances of tones of the types 1, 2 and 3. Given that the frequency of type 1 is any occurrence, and our generated tone sequence is completely random; the occurrence frequency is ~1/N^l~, where ~N~ is the number of different piano tones. The occurrence frequency of number 2 is equal to:

$$\displaystyle \frac{1}{F(2)} = \lim_{n \to \infty} \frac{p_{i+1}^2-p_i^2}{n}$$

Since the occurrence of type 1 is actually a union of occurrences of type 2 and 3, we conclude that ~F(1) = F(2)+F(3)~.

Now that we have connected these three frequencies, let's try to connect the occurrence frequencies of the second and third type.

Since each occurrence of the third type is created from the occurrence of the second type, and by adding a sequence of letters to the end of the occurrence of the second type: more precisely, if the suffix is at the end of the occurrence of the second type, which is at the same time a prefix of the occurrence of the tone sequence of length ~i~, then we need to add ~l-i~ characters in order to get one occurrence of the third type. Since all letter additions are independent and since we add the letters completely randomly, it holds:

$$\displaystyle F(3) = F(2) \sum \frac{1}{N^{l-i}}, i \in [kmp(l), kmp(kmp(l)), kmp(kmp(kmp(l))), \dots]$$

Here, we used the ~kmp~ function, as in the fail function in the KMP algorithm. For more details on KMP, consult additional resources.

Further manipulations get us:

$$\displaystyle \begin{align*} F(1) &= F(2)+F(3) \\ &= F(2) \left(1 + \sum \frac{1}{N^{l-i}}, i \in [kmp(l), kmp(kmp(l)), kmp(kmp(kmp(l))), \dots]\right) \\ F(2) &= \frac{F(1)}{1 + \sum \frac{1}{N^{l-i}}, i \in [kmp(l), kmp(kmp(l)), kmp(kmp(kmp(l))), \dots]} \end{align*}$$

Since the solution we want is ~1/F(2)~, we then get:

$$\displaystyle \begin{align*} \frac{1}{F(2)} &= \frac{1 + \sum \frac{1}{N^{l-i}}, i \in [kmp(l), kmp(kmp(l)), kmp(kmp(kmp(l))), \dots]}{F(1)} \\ &= \frac{1 + \sum \frac{1}{N^{l-i}}, i \in [kmp(l), kmp(kmp(l)), kmp(kmp(kmp(l))), \dots]}{1/N^l} \\ &= N^l + \sum N^i, i \in [kmp(l), kmp(kmp(l)), kmp(kmp(kmp(l))), \dots] \end{align*}$$

The last expression is simply efficiently calculated modulo ~m~. The solution for all prefixes of the tone sequence, which was the original task, is left as an exercise for the reader.