Consider the following problem: given a number $n$, an alphabet $\Sigma$, and a finite language $L$, how many strings of length $n$ in $\Sigma^*$ contain at least one word $w\in L$? E.g. abcgodef contains the word go.

This is a toy problem I want to use to demonstrate the power of an algorithm I developed. I implemented it as a trivial python script, and was able to solve the above problem for $n = 50, \Sigma = [a-z], |L| = 5$ on my laptop.

Does anyone know of an existing technique capable of this? That is, can anyone calculate the answer, or am I the only one? (When I finish my paper, I'll be happy to link it here if people are interested).

Specifically, $L$ was

['the', 'of', 'and', 'you', 'that']
  • $\begingroup$ Please read tour and help center. $\endgroup$
    – Kaveh
    Sep 7, 2015 at 0:36
  • 1
    $\begingroup$ I don't think your toy problem illustrates any "power". It seems you could calculate this using a fairly standard dynamic programming approach, as for every $1\leq i\leq n$ and every prefix of a word in $L$ you'd just need to store how many strings of length $i$ would contain a word of $L$ if you prepended that prefix. $\endgroup$ Sep 7, 2015 at 7:48
  • 2
    $\begingroup$ See Noonan and Zeilberger's exposition of the Goulden-Jackson Cluster method, dx.doi.org/10.1080/10236199908808197 for the general method. $\endgroup$ Sep 10, 2015 at 14:10
  • 1
    $\begingroup$ This is a special case of the problem answered in cstheory.stackexchange.com/questions/8200/… $\endgroup$ Sep 12, 2015 at 3:30

1 Answer 1


This problem can be solved using a fairly standard dynamic programming approach, in time $O(n\cdot \Sigma_{w\in L} |w|)$. This is not counting the complexity of big number arithmetic, which would bring the running time to something like $O(n^2 \log |L| \cdot \Sigma_{w\in L} |w|)$.

I believe the answer to your sample problem is (barring any mistakes in my program):


(Approximately $4.36\cdot 10^{69}$, given that the total number of strings of length $50$ is $5.61\cdot 10^{70}$ this seems reasonable; "or" should be fairly common as a substring.)

In the following $||$ denotes concatenation, $\emptyset$ the empty string and $\bar{w}$ denotes the string $w$ with its first character removed.

$f(w,i)=\begin{cases} \Sigma|^i, & \text{if $w$ contains a word of $L$}.\\ 0, & \text{if $i = 0$}.\\ f(\bar{w}, i), & \text{if $w$ is not a prefix of any word in $L$}.\\ \Sigma_{c\in \Sigma} \space f(w || c, i-1), & \text{otherwise}. \end{cases}$

$f(\emptyset, n)$ is the value you're after. It can be computed (efficiently) using dynamic programming.

  • $\begingroup$ Why don't we continue this discussion in the chat? $\endgroup$ Sep 7, 2015 at 18:07
  • $\begingroup$ Now it's correct... unfortunately... $\endgroup$ Sep 7, 2015 at 18:49
  • $\begingroup$ I'm sorry... :( $\endgroup$ Sep 7, 2015 at 18:51
  • $\begingroup$ I don't understand why the time isn't exponential, though, because of the last case. Also, can you include a proof sketch? $\endgroup$ Sep 7, 2015 at 18:51
  • $\begingroup$ Why doesn't $|\Sigma|$ show up in the time complexity? $\endgroup$ Sep 7, 2015 at 18:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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