Soit une chaîne de caractères d
de longueur n
et un mot t
de longueur m
<n
.
t
dans la chaîne d
(ou -1 s'il est absent). Quelle est sa complexité?t
dans la chaîne d
(ou une liste vide s'il est absent). Quelle est sa complexité?c
appartient au motif t
en temps constant. Proposez un algorithme plus efficace que l'algorithme naïf.d
le texte et t
le motif recherché dans le texteAlgo : recherche_simple Données : d, t : chaînes de caractères n = len (d) m = len (t) i <-- 0 tant que i < n - m: j <-- 0 tant que j < m et d[i+j] = t[j] : j += 1 si j == m : return i sinon : i <-- i + 1
Le deuxième est plus ou moins pareil
Algo : recherche_multiple Données : d, t : chaînes de caractères n = len (d) m = len (t) l = [] i <-- 0 tant que i < n - m: j <-- 0 tant que j < m et d[i+j] = t[j] : j += 1 si j == m : l.append(i) i <-- i + 1 retourner l
Cette approche a un inconvénient : après une comparaison infructueuse, la comparaison suivante débutera à la position i + 1, sans tenir aucun compte de celles qui ont déjà eu lieu à l'itération précédente, à la position i.
Algorithme de Boyer-Moore
L'algorithme de Boyer-Moore examine d'abord la chaîne t
et en déduit des informations permettant de ne pas comparer chaque caractère plus d'une fois.
c
appartient au motif t
en temps constantt
.i = m - 1
c
= d[i]
le dernier caractèrec
n'est pas dans t
, le décalage vaut m
k
la position de la dernière occurrence de c
dans t
k
vaut m-1
(dernier caractère), le décalage vaut m
m - 1 - k
Exemple:
RECHERCHE DE CHAINES CODEES EN MACHINE CHINE CHINE CHINE CHINE CHINE CHINE CHINE CHINE CHINE RECHERCHE DE CHAINES CODEES EN MACHINE
Voici le code :
Algo : recherche améliorée Données : d, t : chaînes de caractères n = len (d) m = len (t) i <-- m - 1 tant que i < n : # PRE-TRAITEMENT c = d[i] si c appartient à t: k <-- dernière_occurrence(c, t) si k == m-1: decalage <-- m sinon decalage <-- m - 1 - k sinon: decalage <-- m # TRAITEMENT j <-- 0 tant que j < m : si t[m - j - 1] = d[i - j] j += 1 sinon break si j = m: retourner i - m + 1 # DECALAGE i <-- i + decalage retourner -1
1. Écrire un algorithme qui compte le nombre de mots dans un texte.
Remarque : On considère comme caractère d'espacement tout caractère qui n'est pas alphanumérique (alphabétique accentué ou non et chiffres).
2. Dessiner l'automate fini correspondant.
1. Écrire un algorithme récursif permettant de savoir si un tableau de caractères est un palindrome (un palindrome se lit "à l'endroit" et "à l'envers" de la même façon, comme par exemple "à l'étape, épate-la!").
Remarque : on ne considère ni la ponctuation, ni les espaces, ni les accents.
Quelle est sa complexité?
2. Pouvez-vous définir un automate fini capable de reconnaître les palindromes?
La solution consisterait à utiliser un automate à pile (non vu en cours). On a alors deux états principaux : un état correspondant à l'empilage des symboles d'entrée, et un état correspondant au dépilage de la pile et à la comparaison avec les symboles d'entrée. La comparaison n'est acceptée que si les symboles sont identiques, et le mot est reconnu lorsque la pile est vide.
1. Donnez l'expression régulière permettant de reconnaître les entiers relatifs et dessiner l'automate fini correspondant.
([+-]?[1-9][0-9]*|0)
2. Donnez l'expression régulière permettant de reconnaître les nombres décimaux (par exemple -3
, 12.3
, -12.34
, +3
, 0.
) et dessiner l'automate fini correspondant.
3. Donnez l'expression régulière expression régulière qui valide les noms de fichiers se terminant par l'une des extensions spécifiées : .jpg
, .png
, ou .gif
et dessiner l'automate fini correspondant.
4. Donnez une expression régulière pour reconnaître les URL commençant par https://.
Correction :
https://[a-zA-Z0-9.-]+\.[a-zA-Z]{2,}
5. Écrivez une expression régulière pour reconnaître la date et l'heure au format YYYY-MM-DD (HH:MM)
Correction :
\d\d\d\d-(0[1-9]|1[12])-(0[1-9]|[12][0-9]|3[0-1]) \((0[0-9]|1[0-9]|2[0-3]):[0-5][0-9]\)
1. Ecrire l'algorithme de reconnaissance de l'expression régulière (a|b)*c
def reconnait(s): final = False for c in s: if final: final = False break if (c not in 'abc'): break if c=='c': final = True return final
2. Dessiner son automate fini
3. Soit G
le graphe orienté décrivant cet automate, chaque arête étant indexée par un caractère. Donner l'algorithme qui indique si oui ou non l'expression est reconnue dans une chaîne s
à partir de son automate fini.
G = { 0 : {'a':0, 'b':0, 'c':1}, 1:{}} def reconnait_auto(s, G): state = 0 for c in s: if c in G[state]: state = G[state][c] else: return False if state == 1: return True else: return False
4. Quelle est sa complexité?
Longueur de la chaîne
1. Même exercice avec l'expression régulière (a|b)*ab
def reconnait_nd(s): transit_a = False final_b = False for c in s: if (c not in 'ab'): break if c=='b': if transit_a: transit_a = False final_b = True else: final_b = False if c == 'a': final_b = False transit_a = True return final_b
2. Dessiner son automate fini
Voir le graphe G
ci-dessous Attention, graphe non déterministe!!
G = { 0 : {'a':(0,1), 'b':(0,)}, 1:{'b':(2,)}, 2:{}}
3. Soit G
le graphe orienté décrivant cet automate, chaque arête étant indexée par un caractère. Donner l'algorithme qui indique si oui ou non l'expression est reconnue dans une chaîne s
à partir de son automate fini.
def reconnait_auto_nd(s, G): states = set((0,)) for c in s: previous_states = states states = set() for state in previous_states: if c in G[state]: next_states = G[state][c] for state in next_states: states.add(state) print(c, states) if len(states) == 0 : return False if 2 in states: return True else: return False
4. Complexité