Number of bit strings of length 8 that do not contain "$100$"? I am thinking the total number of possible strings is $2^8$ and the number of strings with $100$ at the beginning would be $2^8 - 2^3 = 2^5$. Now "$100$" can shift across the string $5$ times going to the right. Is the answer then $2^8 - 2^5 \times 5$? 

Consider 4 exclusive states a string can be in : 


*

*(A) The string contains 100

*(B) The string ends in 10, but doesn't contain 100

*(C) The string ends in 1, but doesn't contain 100

*(D) None of the Above


Now consider a matrix representing transitions from the 4 states.  For example, if a string is in state (B), and the next bit is a 0, then the next state of the string is (A).  The transitions if the next bit is 0 are given by:
$$M_0 = \begin{array} {c|cccc}
  & A & B & C & D \\ \hline
A & 1 & 0 & 0 & 0 \\
B & 1 & 0 & 0 & 0 \\
C & 0 & 1 & 0 & 0 \\
D & 0 & 0 & 0 & 1 \\
\end{array}$$
And the transitions if the next bit is a 1 :
$$M_1 = \begin{array} {c|cccc}
  & A & B & C & D \\ \hline
A & 1 & 0 & 0 & 0 \\
B & 0 & 0 & 1 & 0 \\
C & 0 & 0 & 1 & 0 \\
D & 0 & 0 & 1 & 0 \\
\end{array}$$
And initially the string is empty, so it is in state (D):
$$V = \begin{array} {cccc}
A & B & C & D \\ \hline
0 & 0 & 0 & 1 
\end{array}$$
The states reachable from the string of length $n$ is given by:
$$V(M_0 + M_1)^n$$
So for example, the strings of length 8 will have states:
$$V(M_0 + M_1)^8 = \begin{array} {cccc}
A & B & C & D \\ \hline
168 & 33 & 54 & 1 
\end{array}$$
168 strings will contain 100, 33 will end in 10 but not contain 100, 54 will end in 1 but not contain 100, and there will be 1 more string (the string containing all zeroes).  So there are $2^8 - 168 = 33 + 54 + 1 = 88$ strings not containing 100.
