Différences
Ci-dessous, les différences entre deux révisions de la page.
Les deux révisions précédentes Révision précédente Prochaine révision | Révision précédente | ||
tc_info:2023-td-texte-corr [2023/11/29 12:50] – [Exercice 4 : Expressions régulières] edauce | tc_info:2023-td-texte-corr [2023/12/01 09:49] (Version actuelle) – [Exercice 4 : Expressions régulières] edauce | ||
---|---|---|---|
Ligne 15: | Ligne 15: | ||
i <-- 0 | i <-- 0 | ||
tant que i < n - m: | tant que i < n - m: | ||
- | j < | + | j < |
tant que j < m et d[i+j] = t[j] : | tant que j < m et d[i+j] = t[j] : | ||
j += 1 | j += 1 | ||
Ligne 33: | Ligne 33: | ||
i <-- 0 | i <-- 0 | ||
tant que i < n - m: | tant que i < n - m: | ||
- | j < | + | j < |
tant que j < m et d[i+j] = t[j] : | tant que j < m et d[i+j] = t[j] : | ||
j += 1 | j += 1 | ||
Ligne 39: | Ligne 39: | ||
| | ||
i <-- i + 1 | i <-- i + 1 | ||
+ | retourner l | ||
</ | </ | ||
+ | |||
Cette approche a un inconvénient : après une comparaison infructueuse, | Cette approche a un inconvénient : après une comparaison infructueuse, | ||
- | L' | + | ** Algorithme de Boyer-Moore ** |
+ | |||
+ | L' | ||
- | On regardera une version simplifiée de l'algo de Knuth-Morris-Pratt : | ||
* On suppose qu'on peut tester si un caractère '' | * On suppose qu'on peut tester si un caractère '' | ||
* Le but est de calculer un décalage permettant de ne pas inspecter les positions où il n'y a aucune chance de trouver le motif '' | * Le but est de calculer un décalage permettant de ne pas inspecter les positions où il n'y a aucune chance de trouver le motif '' | ||
* On commence par chercher la position '' | * On commence par chercher la position '' | ||
- | * On inspecte la chaîne | + | * Soit '' |
- | * Soit '' | + | * Si '' |
- | * On note '' | + | * Sinon on note '' |
- | * Le décalage est égal à '' | + | * si '' |
- | * Si on ne trouve rien, le décalage vaut '' | + | * Sinon le décalage est égal à '' |
+ | |||
+ | |||
+ | **Exemple:** | ||
+ | RECHERCHE DE CHAINES CODEES EN MACHINE | ||
+ | CHINE | ||
+ | | ||
+ | CHINE | ||
+ | | ||
+ | CHINE | ||
+ | | ||
+ | CHINE | ||
+ | | ||
+ | | ||
+ | RECHERCHE DE CHAINES CODEES EN MACHINE | ||
- | A illustrer au tableau : | ||
- | {{: | ||
- | Si vous en avez le courage, voici le code : | + | Voici le code : |
< | < | ||
Algo : recherche améliorée | Algo : recherche améliorée | ||
Ligne 66: | Ligne 81: | ||
i <-- m - 1 | i <-- m - 1 | ||
tant que i < n : | tant que i < n : | ||
- | # PRE-TRAITEMENT | + | # PRE-TRAITEMENT |
- | j <-- 0 | + | c = d[i] |
- | tant que j < m - 1: | + | si c appartient à t: |
- | c = d[i - j] | + | k <-- dernière_occurrence(c, |
- | si c appartient à t[:m-j-1] | + | si k == m-1: |
- | k <-- dernière_occurrence(c, | + | |
- | | + | |
- | break | + | |
- | sinon | + | sinon: |
- | j += 1 | + | |
- | si j == m - 1: | + | |
- | decalage <-- m | + | |
# TRAITEMENT | # TRAITEMENT | ||
j <-- 0 | j <-- 0 | ||
Ligne 160: | Ligne 173: | ||
Réponse : '' | Réponse : '' | ||
- | {{ : | + | {{: |
</ | </ | ||
Ligne 167: | Ligne 180: | ||
<note tip> | <note tip> | ||
+ | Réponse : '' | ||
- | '' | + | {{: |
</ | </ | ||
+ | |||
+ | ** 4. Donnez une expression régulière pour reconnaître les URL commençant par {{https:// | ||
+ | |||
+ | Correction : | ||
+ | < | ||
+ | https:// | ||
+ | </ | ||
+ | |||
+ | ** 5. Écrivez une expression régulière pour reconnaître la date et l' | ||
+ | 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]): | ||
+ | </ | ||
+ | |||
==== Exercice 5 ==== | ==== Exercice 5 ==== | ||
+ | |||
1. **Ecrire l' | 1. **Ecrire l' | ||
<code python> | <code python> | ||
Ligne 189: | Ligne 217: | ||
2. **Dessiner son automate fini** | 2. **Dessiner son automate fini** | ||
- | {{ : | + | {{: |
3. **Soit '' | 3. **Soit '' | ||
Ligne 239: | Ligne 267: | ||
2. **Dessiner son automate fini** | 2. **Dessiner son automate fini** | ||
- | {{ : | + | {{: |
Voir le graphe '' | Voir le graphe '' |