Contador n bits que no conienen el patron 010.

[Poles]

Saludos atentos,

Estoy realizando un programa que imprima todas las cadenas de n bits que no contienen el patrón "010",por lo que

donde n es numero de bits

Código PHP:

  function ContadorBits($n,$s = "") 
{  
    if(strlen($s) == $n)  
        {  
                $s." "; 
            echo $s."<br>"; 
             
             
        }else  
        {          
            ContadorBits($n, $s."0");  
            ContadorBits($n, $s."1");// } 
        } 
}  
   

intente colocar un if
//if($n=="010")
echo "";
else
echo $s."<br>";

pero solo funcionaria cuando es d 3 bits
si es d 4 bits tengo que considerar
X010
010X

si es de 5 bits tengo que considerar
XX010
X010X
010XX

donde X puede ser 0 o 1

estos valores no tiene que imprimirme
intente con explode y con chunk split pero no doy
Acabo de empezar con PHP y pues seria muy util su ayuda de antemano muchas gracias

[json]

Échale un ojo a las expresiones regulares:

http://php.net/manual/es/ref.pcre.php

Por ejemplo, en esta función tienes algunos ejemplos que quizá te den una pista:

http://php.net/manual/es/function.preg-match.php

Y también puedes echarle un ojo a algún manual de introducción a las expresiones regulares que encuentres por la red:

http://www.mmfilesi.com/blog/introdu...ulares-en-php/
http://boozox.net/php/manual-complet...ulares-en-php/