12. Given $S$ as a binary string of $10^{4}$ bits containing only $0$ and $1$, a positive integer $k \leqslant 10^{4}$, a $k$-block of $S$ is a substring of $S$ consisting of $k$ consecutive bits. Two $k$-blocks $a_{1} a_{2} \cdots a_{k}=b_{1} b_{2} \cdots b_{k}$ are equal if and only if $a_{i}=b_{i}(i=1$, $2, \cdots, k)$. Consider all $10^{4}$-bit binary strings that contain at most seven different 3-blocks. Find the maximum number of different 10-blocks such a string can contain.
12. The maximum value sought is 504, and the examples that achieve this value include all seven possible 3-blocks except 000.

Let $f(k)$ denote the maximum number of $k$-bit strings that can contain at most seven different 3-blocks.
Clearly, $f(1)=2, f(2)=4, f(3)=7$.
Next, we prove that
$$
f(k) \leqslant f(k-1)+f(k-2)+f(k-3),
$$

with equality holding when the seven possible 3-blocks do not include 000.
By recursion, we get $f(10)=504$.
First, construct a $10^4$-bit string that contains seven different 3-blocks and 504 10-blocks. Add a 1 after each of the 504 10-blocks, then combine these in some order to form a $504 \times 11$-bit string, and append $10^4 - 504 \times 11$ 1s to this string.

Since there are $2^3=8$ possible 3-blocks, assume that a certain 3-block: $abc$ does not appear in any $k$-bit string.

Note that there can be at most $f(k-1)$ strings that do not end in $c$; at most $f(k-2)$ strings that end in $xc$, where $x \neq b$; and at most $f(k-3)$ strings that end in $xbc$, where $x \neq a$.
Therefore, $f(k) \leqslant f(k-1)+f(k-2)+f(k-3)$.