Let $x=x_1x_2\dotsm x_n$ be a binary string. A $k$-substring of $x$ is a period of continuous bits, i.e. $x_ix_{i+1}\dotsm x_{i+k-1}$. I want to count the number of all the binary strings whose any two arbitrary over-lapping $k$-substrings is never Reverse-Complement 【Reverse-Complement means reverse one of substring and add to the other (the bit-sum modulo 2), a $k$-length string with all bits equal to 1 is obtained】.
Is there a theory about counting the number of such binary strings?
The even length substrings which equal their own reverse complement are precisely the even length palindromes when you reverse every other letter in $x$. Therefore you are looking for the number of strings of length $n$ that do not contain any palindromes of length $2\ell := 2\lceil k / 2 \rceil$. Let's call this number $f_\ell(n)$.
Counting the number of words of length $n$ avoiding length $k$ palindromes sounds like a very natural problem in combinatorics on words, but I couldn't find anything after a quick google search, so I'm not sure there exists a nice exact formula. However you can find some rough bounds on its behavior for variable $\ell$ and $n$ using counting and probabilistic arguments.
For example, there is an upper bound of $f_\ell(n) \leq (2^{2\ell} - 2^\ell)^{\lceil n / 2\ell\rceil} \approx e^{-(2^{-\ell-1}/\ell) \cdot n}\cdot 2^n$, because there are $2^{2\ell} - 2^\ell$ possibilities for each segment of length $2\ell$.
For a lower bound, note that cyclic strings of length $2^{\ell-1}$ are expected to have half a palindrome. Thus there are at least $$\frac{2^{2^{\ell-1}}}{2\cdot2^{4\ell}}$$ different strings of length $2^{\ell-1}$ same length $2\ell$ prefix and suffix, which we can concatenate arbitrarily without introducing palindromes. This gives a lower bound of $$f_\ell(n) \geq \left(\frac{2^{2^{\ell-1}}}{2\cdot2^{4\ell}}\right)^{\lfloor n / 2^{\ell-1}\rfloor } \approx 2^{-(4\ell+1)2^{-\ell+1}\cdot n}\cdot 2^n.$$ Therefore $f_\ell(n) = 2^{n(1-2^{-\ell + o(\ell)})+O(2^\ell)}$.
