Résumé
vignette|Illustration de la recherche de la sous-chaîne "long des" dans la première strophe du poème Chanson d'automne de Paul Verlaine. En algorithmique du texte, un algorithme de recherche de sous-chaîne est un type d'algorithme de recherche qui a pour objectif de trouver une chaîne de caractères dans un texte. Le problème de recherche d'une sous-chaîne intervient dans beaucoup d'applications. Par exemple, dans un logiciel de traitement de texte, ou dans un navigateur internet, l'utilisateur peut rechercher une chaîne de caractères dans un document, ou une page Internet, en vue de remplacer un mot par un autre (par exemple, remplacer toues les occurrences du mot "rêve" par le mot "songe"). La plupart des langages de programmation proposent des fonctions pour effectuer une telle recherche ; par exemple en Python, on écrit chaine in texte pour tester si la chaîne apparaît dans le texte. Par extension, on peut considérer aussi le problème de trouver toutes les occurrences d'un mot, ou alors de compter le nombre d'occurrences d'une chaîne dans un texte. L'algorithme naïf consiste consiste à faire glisser le motif le long du texte. A début, le motif se trouve aligné avec le début du texte. Par exemple si l'on cherche la chaîne longs des dans le texte les sanglots longs des violons de l'automne blessent mon cœur d'une langueur monotone on considère l'alignement suivant : les sanglots longs des violons de l'automne blessent mon cœur d'une langueur monotone. longs des On compare caractère après caractère le motif et le texte. Le première caractère est l. Mais le deuxième caractère est différent. On fait alors glisser le motif d'une case vers la droite. les sanglots longs des violons de l'automne blessent mon cœur d'une langueur monotone. longs des On compare caractère après caractère le motif et le texte à partir du second caractères. Le caractère e et l sont différents. On continue donc à glisser le motif. les sanglots longs des violons de l'automne blessent mon cœur d'une langueur monotone.
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.
Cours associés (12)
CS-214: Software construction
Learn how to design and implement reliable, maintainable, and efficient software using a mix of programming skills (declarative style, higher-order functions, inductive types, parallelism) and fundam
CS-308: Introduction to quantum computation
The course introduces the paradigm of quantum computation in an axiomatic way. We introduce the notion of quantum bit, gates, circuits and we treat the most important quantum algorithms. We also touch
CS-330: Artificial intelligence
Introduction aux techniques de l'Intelligence Artificielle, complémentée par des exercices de programmation qui montrent les algorithmes et des exemples de leur application à des problèmes pratiques.
Afficher plus
Séances de cours associées (52)
Python Basics: Fonctions et Listes
Introduit les bases de Python comme les types, les fonctions, les conditions, les boucles et les listes, avec des exemples de manipulation de chaîne et d'opérations de liste.
Structures de données élémentaires : piles, files d'attente, listes liées
Couvre les piles, les files d'attente et les listes liées, en mettant l'accent sur l'efficacité et les structures dynamiques.
Projets d'ingénierie Vue d'ensemble
Fournit un aperçu des projets d'ingénierie, des conseils de dépannage et des démonstrations pratiques sur le traitement du signal et l'intégration Arduino.
Afficher plus
Publications associées (48)

In Medio Stat Virtus: Combining Boolean and Pattern Matching

Giovanni De Micheli, Alessandro Tempia Calvino, Gianluca Radi

Technology mapping transforms a technology-independent representation into a technology-dependent one given a library of cells. This process is performed by means of local replacements that are extracted by matching sections of the subject graph to library ...
2024

List Ordered Statistics Decoders for Polar Codes

Andreas Peter Burg, Yifei Shen, Leyu Zhang, Chuan Zhang

The de-facto standard decoding algorithm for polar codes, successive cancellation list (SCL) decoding, is a breadth-first search algorithm. By keeping a list of candidate codewords, SCL decoding improves the performance as the list size L increases. Howeve ...
IEEE2022

An Analysis of Super-Net Heuristics in Weight-Sharing NAS

Mathieu Salzmann, Kaicheng Yu

Weight sharing promises to make neural architecture search (NAS) tractable even on commodity hardware. Existing methods in this space rely on a diverse set of heuristics to design and train the shared-weight backbone network, a.k.a. the super-net. Since he ...
IEEE COMPUTER SOC2022
Afficher plus
Concepts associés (9)
Substring
In formal language theory and computer science, a substring is a contiguous sequence of characters within a string. For instance, "the best of" is a substring of "It was the best of times". In contrast, "Itwastimes" is a subsequence of "It was the best of times", but not a substring. Prefixes and suffixes are special cases of substrings. A prefix of a string is a substring of that occurs at the beginning of ; likewise, a suffix of a string is a substring that occurs at the end of .
Filtrage par motif
Le filtrage par motif est la vérification de la présence de constituants d'un motif par un programme informatique, ou parfois par un matériel spécialisé. Par contraste avec la reconnaissance de forme, les motifs sont complètement spécifiés. De tels motifs concernent conventionnellement des séquences ou des arbres. Par exemple "HDpdf" peut signifier : "Toute chaîne contenant HD et se terminant par pdf".
Trie (informatique)
thumb|250px|Un trie pour les clés "A", "to", "tea", "ten", "ted", "i", "in", et "inn". En informatique, un ou une trie (prononcé ou ) ou arbre préfixe, est une structure de données ayant la forme d'un arbre enraciné. Il est utilisé pour stocker une table associative où les clés sont généralement des chaînes de caractères. Contrairement à un arbre binaire de recherche, aucun nœud dans le trie ne stocke la chaîne à laquelle il est associé. C'est la position du nœud dans l'arbre qui détermine la chaîne correspondante.
Afficher plus
MOOCs associés (1)
Introduction to optimization on smooth manifolds: first order methods
Learn to optimize on smooth, nonlinear spaces: Join us to build your foundations (starting at "what is a manifold?") and confidently implement your first algorithm (Riemannian gradient descent).