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