TITLE: How to calculate number of unique strings given a blacklist of avoided substrings.
QUESTION [0 upvotes]: If you use the lowercase alphabet a-z plus the numbers 0-9 to construct a random string, the question is how to mathematically figure out in advance (i.e. without doing brute force approach) how many possibilities you can have given that you want to blacklist a few words so they don't appear in the text. So there are $26 + 10 = 36$ characters.
Say all strings are 256 characters long. Say the blacklist words we want to avoid are:
abc
defg
hijk
lmnop
qrs
tuv
wx
yz

If there's no blacklist, then the value is simply $36^n$, or $36^{256}$ in this case.
But if there is a blacklist, wondering how to calculate the number of possible strings of length $n$ or 256. I understand how to create an algorithm for this, but not how to calculate how many values it contains.
My attempt is as follows.... Say each value $v$ can appear at any position $i$ in the string of length $n$ up to $n-l(v)$, where $l(v)$ is the length of $v$. But you also have to take into account that the strings can't overlap, and all the combinations of them showing up together or not. You also want to consider repeats, so randomrandomabcrandomrandomabcrandom sort of thing. Etc.. Now I'm starting to get lost. I'd have to try writing out an algorithm to see how it works.
I would like to learn how to solve these kinds of problems better, not really sure how to avoid the brute force approach of trying out variations and possibilities.

REPLY [1 votes]: For every finite (and valid) string $\alpha$ we can define $f(\alpha)$ as 
the longest prefix of a blacklisted word that is a suffix of $\alpha$. Knowing only $f(\alpha)$ (and the sturcture of the blacklist), we can determine for each character $x$ whether $\alpha x$ is valid (namely, whether $f(\alpha)x$ is not a blacklisted word), and if so, what $f(\alpha x)$ is.
For each prefix $p$ of at least one blacklisted word (including the empty prefix, but none of the complete words), let $F(n,p)$ be the number of valid strings $\alpha$  of length $n$ and such that $f(\alpha)=p$. As described above, we can compute $F(n,p)$ from all $F(n-1,p')$. So if there are $m$ prefixes, the $m$-dimensional vector $F_n:=(f(n,p_1),\ldots,f(n,p_m))^T$ is obtained from $F_{n-1}$ by a matrix multiplication,
$$ F_n=AF_{n-1}.$$
Note that $F_0$ is the vector with $1$ in the entry corresponding to the empty prefix and the final result we want is the sum of all components of  $F_n$, or its scalar product with $(1,1,\ldots,1)^T$. The behaviour of this for large $n$ is governed by the largest eigenvalue $\lambda$ of $A$ in that there is a constant $c$ such that there are roughly $$c\lambda^n$$ valid strings of length $n$.

In your specific example, we'd have to deal with a $19\times 19$ matrix, which may be tedious. A very rough lower bound however is this (for that specific list of words): At any point, at most one character is "forbidden" (this property may not hold for a different blacklist). Hence there are at least $35^n$ valid words. While this is very rough and the difference between $35^n$ and $36^n$ is enormous for large $n$, it is perhaps a good enough figure for an application you may have in mind.
{"set_name": "stack_exchange", "score": 0, "question_id": 3117155}