Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Algorithmes de recherche dans les chaines de caracteres

Page C structures de données et la STL Algorithmes de recherche dans les cha? nes de caractères Quand on utilise des cha? nes de caractères on a souvent besoin d'examiner une cha? ne pour y rechercher une sous-cha? ne donnée Une telle opération de recherche existe dans tous les logiciels de traitement de textes ainsi d ? ailleurs que dans toutes les réalisations du type de données abstrait cha? ne de caractères Lorsqu'on manipule de longs textes on doit réaliser cette opération aussi e ?cacement que possible Nous nous concentrerons ici sur quatre algorithmes classiques de recherche de patron en anglais pattern- matching qui examinent une cha? ne pour y trouver une sous-cha? ne donnée Recherche simple La réalisation de l'opération ?nd pour prendre une des opérations de recherche associées au type string permet d ? illustrer l'algorithme de recherche de patron le plus simple La ?gure illustre cet algorithme pour la recherche de la sous-cha? ne ??abc ? dans la cha? ne ??ababc ? le caractère ?? ? marque les positions dans le patron et dans la cha? ne o? la comparaison est e ?ectuée On commence au début de la cha? ne et de la sous-cha? ne ou patron et on compare les premiers caractères Ils correspondent on compare alors les deuxièmes caractères ils correspondent aussi On compare donc les troisièmes caractères comme ils ne correspondent pas indiqué par un astérisque on revient au deuxième caractère de la cha? ne et au premier caractère du patron et on répète le processus ababc ababc abc abc ababc abc ababc abc ababc abc ababc abc ababc abc Cha? ne de caractères Patron Comparaisons Figure Recherche de patron Cet algorithme est simple et facile à programmer La fonction RechercheSimple ci-dessous illustre cet algorithme de façon plus détaillée int RechercheSimple const string Patron const string Texte int carac pat longueurPatron longueurTexte longueurPatron Patron size longueurTexte Texte size pat if longueurPatron longueurTexte carac do if Patron pat Texte carac pat carac else carac carac - pat avance dans Texte pat if while pat longueurPatron carac longueurTexte if if pat longueurPatron trouvé return carac - longueurPatron else return - RechercheSimple Sous-produit d ? une recherche d ? emploi ? Ph Gabrini CChapitre Page Dans la boucle do-while les caractères de la cha? ne et du patron sont comparés un à un chaque fois qu'on note une di ?érence des caractères on repart au début du patron après avoir reculé dans la cha? ne Dans le pire des cas c ? est-à-dire celui o? le patron ne se trouve pas dans la cha? ne chacun des p caractères du patron sera comparé aux t caractères de la cha? ne texte par exemple si nous cherchons ??hipi ? dans ??hipahipbhipchipdhipehipfhipg ? La complexité temporelle de l'algorithme est donc O pt Algorithme de Knuth-Morris-Pratt En examinant la recherche de patron de la ?gure on se rend facilement compte que certaines comparaisons sont inutiles Par exemple la comparaison de l'étape est inutile car le second caractère de la