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.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?
On cherche à exprimer une distance entre deux chaînes de caractères.
Une distance entre 2 textes d1 et d2 est telle que :
La distance de Hamming entre deux chaînes de même taille est définie comme le nombre de caractères non appariés. Ainsi la distance de Hamming entre "passoire" et "pastèque" est égale à 4. Peut-on généraliser cette distance à des chaînes de taille différente?
La distance d’édition est définie, pour deux chaînes de longueur quelconque, comme le nombre minimal d’opérations permettent de transformer d1 en d2, avec les opérations suivantes :
Il existe différentes manières de transformer la chaîne d1 en d2. On peut par exemple supprimer tous les caractères de d1 et insérer tous les caractères de d2, mais c'est rarement le nombre d'opérations optimal (|d1|+|d2|).