Soit une chaîne de caractères d de longueur n et un mot t de longueur m<n.

1. Donner l'algorithme naïf retournant la position de la première occurrence du mot t dans la chaîne d (ou -1 s'il est absent). Quelle est sa complexité?
2. Donner de même l'algorithme retournant la position de toutes les occurrences du mot t dans la chaîne d (ou une liste vide s'il est absent). Quelle est sa complexité?
3. On suppose qu'on peut tester si un caractère c appartient au motif t en temps constant. Proposez un algorithme plus efficace que l'algorithme naïf.

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?

• Les langages réguliers sont des types de langages formels qui peuvent être reconnus par un automate fini.
• Le langage des expressions régulières est un langage régulier qui permet de décrire des motifs (c'est à dire des classes de mots) dans une chaîne de caractère.

1. Donnez l'expression régulière permettant de reconnaître les entiers relatifs et dessiner l'automate fini correspondant.
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://…
5. Écrivez une expression régulière pour reconnaître la date et l'heure au format YYYY-MM-DD (HH:MM)

1. Ecrire l'algorithme de reconnaissance de l'expression régulière (a|b)*c
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.
4. Quelle est sa complexité?

1. Ecrire l'algorithme de reconnaissance de l'expression régulière (a|b)*ab
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.
4. Quelle est sa complexité?