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 '15 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 '15 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 '15 at 14:10
  • 1
    $\begingroup$ This is a special case of the problem answered in cstheory.stackexchange.com/questions/8200/… $\endgroup$ Sep 12 '15 at 3:30

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 '15 at 18:07
  • $\begingroup$ Now it's correct... unfortunately... $\endgroup$ Sep 7 '15 at 18:49
  • $\begingroup$ I'm sorry... :( $\endgroup$ Sep 7 '15 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 '15 at 18:51
  • $\begingroup$ Why doesn't $|\Sigma|$ show up in the time complexity? $\endgroup$ Sep 7 '15 at 18:59

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.