How to calculate no. of binary strings containing substring “11011”? I need to calculate no of possible substrings containing "11011" as a substring. I know the length of the binary string.
Eg: for a string of length 6, possible substrings are: 110110 110111 111011 011011
I just need the number of possible combinations, not enumerate all of them.
 A: A general plan for this kind of tasks is:


*

*You're looking for the number of strings of a given length in a regular language.

*Construct a deterministic finite automaton that recognizes the language.

*Derive from this automaton a set of first-order recurrence equations for $a_{n,k}=$ "the number of strings of length $n$ that take the automaton from the initial state to state $k$".

*Write the recurrence as a matrix equation: $\vec a_{n+1} = B \vec a_n$, where $\vec a_0$ has $1$ in the $a_{0,0}$ position (assuming the initial state is state $0$), and $0$ in every other $a_{0,k}$.

*Then $\vec a_{n} = B^n \vec a_0$ where $B^n$ can be computed relatively quickly using exponentiation by squaring and $\vec a_{n}$ gives you the number of length-$n$ strings that end in each of the states. Sum over the accepting states.
Alternatively, try to diagonalize $B$ and find a closed-form Binet-like formula for each $a_{n,k}$. This tends to end up fairly horrible if the language is at all complex, though.
The method is particularly suited when the language is something like "all strings that contain (or don't contain) such-and-such as a substring", where the DFA is known to be small (with only as many states as there are symbols in the search target, plus 1).
A: The Goulden-Jackson cluster method handles many questions of the form: 

How many strings of a particular length avoid such-and-such patterns?

The method efficiently gives a generating function whose coefficients are the number of strings of a particular length avoiding the patterns. (My opinion is that learning this general method is easier than almost any individual instance of a pattern-avoidance problem.) In your case for binary strings avoiding the single string 11011, G-J gives the generating function
$$-{\frac {{x}^{4}+{x}^{3}+1}{{x}^{5}+{x}^{4}-{x}^{3}+2\,x-1}}.$$
The first few terms of this generating function are 
$$1+2\,x+4\,{x}^{2}+8\,{x}^{3}+16\,{x}^{4}+31\,{x}^{
5}+60\,{x}^{6}+116\,{x}^{7}+225\,{x}^{8}+437\,{x}^{9}+849\,{x}^{10}
+\cdots.$$
So, in particular the number of strings of length 5 containing 11011 is $2^5-31=1$ (namely 11011 itself), and the number of strings of length 6 containing 11011 is $2^6-60=4$ (as you illustrated), and the number of strings of length 10 containing 11011 is $2^{10}-849=175$. Of course, since the denominator of this generating function does not factor nicely, it will be tough to get an exact count for your strings. Even so, it's pretty straightforward from here to get recurrence relations for your tallies, good approximations, or whatever else you usually do with generating functions.
