Bonjour,
Je recherche un algo qui me permette de déterminer l'inclusion d'une séquence binaire dans une autre et optionnellement combien de fois.
Par exemple, soit la séquence Db : 1101100, et C la séquence de recherche : 110.
Je voudrais savoir si C est inclu dans DB.
J'ai déjà exploré les algo de détection de sous séquence à l'intérieur de séquence comme Knuth-Morris-Pratt ou les algo de calcul de distance entre termes. Mais tout ceci est trop lourd à mettre en place (dans mon cas). Je me suis donc tourner vers des solutions de relation entre les nombres comme PGCD ou relation BEZOUT. Ces solutions me satisfont en terme de complexité, mais n'offrent pas de solution probante (dans le cas où C est un nombre premier).
Afin de clarifier un peu, je vais ajouter d'autres exemples:
Soit DB 1101100 et C 110; C est inclus dans DB 2 fois
Soit DB 1101100 et C 1101; C est inclus dans DB 1 fois
Soit DB 1101100 et C 11000; C est inclus dans DB 0 fois
bien évidement, une solution serait de faire une comparaison binaire (ET) avec un décallage tant que C < DB. Mais j'aimerais trouver une solution un peu plus élégante.
Voilà j'espère avoir été suffisament clair dans mes explications, je vous souhaite une excellente journée.
Stéphane
Partager