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.
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.
Understanding of the principles and applications of functional programming, the fundamental models of program
execution, application of fundamental methods of program composition, meta-programming thr
Discrete mathematics is a discipline with applications to almost all areas of study. It provides a set of indispensable tools to computer science in particular. This course reviews (familiar) topics a
L'objectif de ce cours est d'introduire les étudiants à la pensée algorithmique, de les familiariser avec les fondamentaux de l'Informatique et de développer une première compétence en programmation (
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 .
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".
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.
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).
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.
As it has become easier and cheaper to collect big datasets in the last few decades, designing efficient and low-cost algorithms for these datasets has attracted unprecedented attention. However, in m