-5
$\begingroup$

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']
Improve this question
$\endgroup$
4
  • $\begingroup$ Please read tour and help center. $\endgroup$
    – Kaveh
    Commented 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$
    – Tom van der Zanden
    Commented 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$
    – András Salamon
    Commented Sep 10, 2015 at 14:10
  • 1
    $\begingroup$ This is a special case of the problem answered in cstheory.stackexchange.com/questions/8200/… $\endgroup$
    – David Eppstein
    Commented Sep 12, 2015 at 3:30

1 Answer 1

Reset to default
0
$\begingroup$

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):

4361583841553844512216859806590291394203513538220428254669943773111822

(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.

Improve this answer
$\endgroup$
9
  • $\begingroup$ Why don't we continue this discussion in the chat? $\endgroup$
    – Tom van der Zanden
    Commented Sep 7, 2015 at 18:07
  • $\begingroup$ Now it's correct... unfortunately... $\endgroup$
    – Elliot Gorokhovsky
    Commented Sep 7, 2015 at 18:49
  • $\begingroup$ I'm sorry... :( $\endgroup$
    – Tom van der Zanden
    Commented 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$
    – Elliot Gorokhovsky
    Commented Sep 7, 2015 at 18:51
  • $\begingroup$ Why doesn't $|\Sigma|$ show up in the time complexity? $\endgroup$
    – Elliot Gorokhovsky
    Commented 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.