Puis-je utiliser des expressions régulières pour rechercher des multiples d'un nombre?

import re

# For real example,
# construction of a chain with integers multiples of 48 
# and integers not multiple of 48.
from random import *
w   =   [ 48*randint( 1,10) for j in xrange(10) ]
w.extend( 48*randint(11,20) for j in xrange(10) )
w.extend( 48*randint(21,70) for j in xrange(10) )
a = [ el if el%48!=0 else el+1 for el in sample(xrange(1000),40) ]
w.extend(a)
shuffle(w)
texte = [ ''.join(sample('     abcdefghijklmonopqrstuvwxyz',randint(1,7))) for i in xrange(40) ]
X = ''.join(texte[i]+str(w[i]) for i in xrange(40))


# Searching the multiples of 48 in the chain X
def mult48(match):
    g1 = match.group()
    if int(g1)%48==0:
        return ( g1, X[0:match.end()] )
    else:
        return ( g1, 'not multiple')

for match in re.finditer('\d+',X):
    print '%s  %s\n' % mult48(match)

Tout multiple est difficile, mais voici une regex (style python) qui correspond aux 200 premiers multiples de 48.

0$|1(?:0(?:08$|56$)|1(?:04$|52$)|2(?:00$|48$|96$)|3(?:44$|92$)|4(?:4(?:$|0$)|88$\
)|5(?:36$|84$)|6(?:32$|80$)|7(?:28$|76$)|8(?:24$|72$)|9(?:2(?:$|0$)|68$))|2(?:0(\
?:16$|64$)|1(?:12$|60$)|2(?:08$|56$)|3(?:04$|52$)|4(?:0(?:$|0$)|48$|96$)|5(?:44$\
|92$)|6(?:40$|88$)|7(?:36$|84$)|8(?:32$|8(?:$|0$))|9(?:28$|76$))|3(?:0(?:24$|72$\
)|1(?:20$|68$)|2(?:16$|64$)|3(?:12$|6(?:$|0$))|4(?:08$|56$)|5(?:04$|52$)|6(?:00$\
|48$|96$)|7(?:44$|92$)|8(?:4(?:$|0$)|88$)|9(?:36$|84$))|4(?:0(?:32$|80$)|1(?:28$\
|76$)|2(?:24$|72$)|3(?:2(?:$|0$)|68$)|4(?:16$|64$)|5(?:12$|60$)|6(?:08$|56$)|7(?\
:04$|52$)|8(?:$|0(?:$|0$)|48$|96$)|9(?:44$|92$))|5(?:0(?:40$|88$)|1(?:36$|84$)|2\
(?:32$|8(?:$|0$))|3(?:28$|76$)|4(?:24$|72$)|5(?:20$|68$)|6(?:16$|64$)|7(?:12$|6(\
?:$|0$))|8(?:08$|56$)|9(?:04$|52$))|6(?:0(?:00$|48$|96$)|1(?:44$|92$)|2(?:4(?:$|\
0$)|88$)|3(?:36$|84$)|4(?:32$|80$)|5(?:28$|76$)|6(?:24$|72$)|7(?:2(?:$|0$)|68$)|\
8(?:16$|64$)|9(?:12$|60$))|7(?:0(?:08$|56$)|1(?:04$|52$)|2(?:0(?:$|0$)|48$|96$)|\
3(?:44$|92$)|4(?:40$|88$)|5(?:36$|84$)|6(?:32$|8(?:$|0$))|7(?:28$|76$)|8(?:24$|7\
2$)|9(?:20$|68$))|8(?:0(?:16$|64$)|1(?:12$|6(?:$|0$))|2(?:08$|56$)|3(?:04$|52$)|\
4(?:00$|48$|96$)|5(?:44$|92$)|6(?:4(?:$|0$)|88$)|7(?:36$|84$)|8(?:32$|80$)|9(?:2\
8$|76$))|9(?:0(?:24$|72$)|1(?:2(?:$|0$)|68$)|2(?:16$|64$)|3(?:12$|60$)|4(?:08$|5\
6$)|5(?:04$|52$)|6(?:$|0$))

Ici, vous allez (dans la syntaxe PCRE de PHP):

preg_match('/^(0*|(1(01*?0)*?1|0)+?0{4})$/', decbin($number));

Une généralisation de votre question est de demander si x est une chaîne représentant un multiple de n dans la base b . C'est la même chose que de demander si le reste de x divisé par n est 0. Vous pouvez facilement créer une DFA pour calculer cela.

Créer un DFA avec < em> n états, numérotés de 0 à n - 1. L'état 0 est à la fois l'état initial et l'état d'acceptation unique. Chaque état aura B les transitions sortantes, une pour chaque symbole de l'alphabet (puisque la base- b vous donne b chiffres pour travailler avec).

Chaque état représente le reste de la partie de x nous avons vu jusqu'à présent, divisé par n. c'est pourquoi nous avons n d'entre eux (divisant un nombre par n produit un reste compris entre 0 et n - 1), et aussi pourquoi l'état 0 est l'état d'acceptation.

puisque les chiffres de x sont traités de gauche à droite, si nous avons un numéro y à partir des premiers chiffres de x < / em> et lisez le chiffre d , nous obtenons la nouvelle valeur de y de yb + d. mais plus important encore, le reste r modifie ( rb + d ) mod n. donc nous savons maintenant comment nous savons maintenant comment Connectez les arcs de transition et complétez la DFA.

Vous pouvez le faire pour tout n et b . Ici, par exemple, est celui qui accepte des multiples de 18 à base-10 (états sur les lignes, entrées sur les colonnes): xxx

celles-là sont vraiment fastidieuses comme N et b obtenir plus grand, mais vous pouvez évidemment écrire un programme pour les générer pour vous, sans problème.