<p>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|)$.</p>

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

<blockquote>
  <p>4361583841553844512216859806590291394203513538220428254669943773111822</p>
</blockquote>

<p>(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.)</p>

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

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

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

CC BY-SA 3.0
2015-09-07T18:07:43.657Z
Why don't we continue this discussion in [the chat](http://chat.stackexchange.com/rooms/9446/theory-salon)?
Tom van der Zanden
CC BY-SA 3.0
2015-09-07T18:49:22.593Z
Now it's correct... unfortunately...
Elliot Gorokhovsky
CC BY-SA 3.0
2015-09-07T18:51:14.557Z
I'm sorry... :(
Tom van der Zanden
CC BY-SA 3.0
2015-09-07T18:51:55.480Z
I don't understand why the time isn't exponential, though, because of the last case. Also, can you include a proof sketch?
Elliot Gorokhovsky
CC BY-SA 3.0
2015-09-07T18:59:39.827Z
Why doesn't $|\Sigma|$ show up in the time complexity?
Elliot Gorokhovsky
CC BY-SA 3.0
2015-09-07T19:07:17.223Z
The reason the time isn't exponential is because of \emph{dynamic programming} (this is a very important technique, you should learn it!). Intermediate values can be memorized and reused. You can download the [source code here](http://pastebin.ca/3155427). You are right, to be completely correct $|\Sigma|$ should show up in the running time. I ignored it because it is small compared to the rest.
Tom van der Zanden
CC BY-SA 3.0
2015-09-07T19:09:19.967Z
OK, so if it was naively implemented it would take exponential time, but with memoization it's polynomial.
Elliot Gorokhovsky
CC BY-SA 3.0
2015-09-07T19:17:04.413Z
Last bonus question: can your method be modified to find how many strings contain exactly 2 words?
Elliot Gorokhovsky
CC BY-SA 3.0
2015-09-07T19:23:28.380Z
Yes, but please don't ask me to implement it because it would be really annoying :-)
Tom van der Zanden
CC BY-SA 3.0
2015-09-07T17:44:29.703Z
2015-09-07T18:44:33.203Z
2015-09-07T18:44:33.203Z
Tom van der Zanden
<p>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. <code>abcgodef</code> contains the word <code>go</code>.</p>

<p>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. </p>

<p>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).</p>

<hr>

<p>Specifically, $L$ was</p>

<pre><code>['the', 'of', 'and', 'you', 'that']
</code></pre>

CC BY-SA 3.0
2015-09-07T00:36:48.920Z
Please read [tour] and [help/on-topic].
Kaveh
CC BY-SA 3.0
2015-09-07T07:48:07.540Z
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.
Tom van der Zanden
CC BY-SA 3.0
2015-09-10T14:10:12.417Z
See Noonan and Zeilberger's exposition of the Goulden-Jackson Cluster method, http://dx.doi.org/10.1080/10236199908808197 for the general method.
András Salamon
CC BY-SA 3.0
2015-09-12T03:30:51.577Z
This is a special case of the problem answered in http://cstheory.stackexchange.com/questions/8200/counting-words-accepted-by-a-regular-grammar
David Eppstein
<co.combinatorics>
A simple challenge
Elliot Gorokhovsky
# A simple challenge

(Asked by: username_0 on 2015-09-06)

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']

**Tags:** co.combinatorics

> **Comments:**
> **username_1**: Please read [tour] and [help/on-topic].  
> **username_2**: 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.  
> **username_3**: See Noonan and Zeilberger's exposition of the Goulden-Jackson Cluster method, http://dx.doi.org/10.1080/10236199908808197 for the general method.  
> **username_4**: This is a special case of the problem answered in http://cstheory.stackexchange.com/questions/8200/counting-words-accepted-by-a-regular-grammar  

---

## 1 answers

### Answer by username_2 on 2015-09-07. Score: 0 | Accepted answer

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.

> **Comments:**
> **username_2**: Why don't we continue this discussion in [the chat](http://chat.stackexchange.com/rooms/9446/theory-salon)?  
> **username_0**: Now it's correct... unfortunately...  
> **username_2**: I'm sorry... :(  
> **username_0**: I don't understand why the time isn't exponential, though, because of the last case. Also, can you include a proof sketch?  
> **username_0**: Why doesn't $|\Sigma|$ show up in the time complexity?  
> **username_2**: The reason the time isn't exponential is because of \emph{dynamic programming} (this is a very important technique, you should learn it!). Intermediate values can be memorized and reused. You can download the [source code here](http://pastebin.ca/3155427). You are right, to be completely correct $|\Sigma|$ should show up in the running time. I ignored it because it is small compared to the rest.  
> **username_0**: OK, so if it was naively implemented it would take exponential time, but with memoization it's polynomial.  
> **username_0**: Last bonus question: can your method be modified to find how many strings contain exactly 2 words?  
> **username_2**: Yes, but please don't ask me to implement it because it would be really annoying :-)  

---

