Metraipolis › archive › dc_2b7ef514fab3

Algorithme de Knuth-Morris-Pratt — Wikipedia (fr)

Source
Wikipedia (fr)
Original
https://fr.wikipedia.org/wiki/Algorithme_de_Knuth-Morris-Pratt
License (as archived)
CC-BY-SA-4.0
Archived
2026-10-17T11:43:37.935Z
SHA-256 of the archived text
c62500c6b20a3a726e4f1d74804db83b23459012d2524796c900006cadb3b270
Stable URL of this page
https://metraipolis.com/documento/dc_2b7ef514fab3

How to cite

Algorithme de Knuth-Morris-Pratt — Wikipedia (fr) — Wikipedia (fr), https://fr.wikipedia.org/wiki/Algorithme_de_Knuth-Morris-Pratt (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_2b7ef514fab3 (Metraipolis archive dc_2b7ef514fab3, sha256 c62500c6b20a3a726e4f1d74804db83b23459012d2524796c900006cadb3b270)
BibTeX
@misc{dc2b7ef514fab3,
  title = {Algorithme de Knuth-Morris-Pratt — Wikipedia (fr)},
  howpublished = {Wikipedia (fr)},
  url = {https://fr.wikipedia.org/wiki/Algorithme_de_Knuth-Morris-Pratt},
  note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_2b7ef514fab3; sha256 c62500c6b20a3a726e4f1d74804db83b23459012d2524796c900006cadb3b270},
  year = {2026}
}

Archived text

Reproduced under CC-BY-SA-4.0. Attribution: Wikipedia (fr), https://fr.wikipedia.org/wiki/Algorithme_de_Knuth-Morris-Pratt. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

En informatique, l'algorithme de Knuth-Morris-Pratt (ou d'une manière plus courte l'algorithme KMP) est un algorithme de recherche de sous-chaîne de caractères. Il permet de trouver les occurrences d'une chaîne P {\displaystyle P} (ou aussi appelé motif) dans un texte T {\displaystyle T} avec une complexité linéaire O ( | P | + | T | ) {\displaystyle O(|P|+|T|)} dans le pire cas, où | P | {\displaystyle |P|} et | T | {\displaystyle |T|} sont respectivement les longueurs (nombres de caractères) de la chaîne P {\displaystyle P} et du texte T {\displaystyle T} et O ( ) {\displaystyle O()} est une notation asymptotique de Landau. De plus la constante dans le O ( ) {\displaystyle O()} ne dépend pas de la taille de l'alphabet. Sa particularité réside en un prétraitement de la chaîne, qui fournit une information suffisante pour déterminer où continuer la recherche en cas de non-correspondance. Ainsi l'algorithme ne ré-examine pas les caractères qui ont été vus précédemment, et donc limite le nombre de comparaisons nécessaires. Plus précisément, la complexité du prétraitement est en O ( | P | ) {\displaystyle O(|P|)} , et la recherche proprement dite est en O ( | T | ) {\displaystyle O(|T|)} . L'algorithme a été conçu en 1970 par Knuth et Pratt, et dans un autre contexte, par Morris, et publié conjointement en 1977. Indépendamment Matiyasevich avait déjà obtenu dès 1969 un algorithme similaire, codé par une machine de Turing à deux dimensions[pas clair], en étudiant un problème de reconnaissance d'occurrence de chaîne.

Tema degli esploratori: scibile generale (retro-catalogo completo della fonte, senza filtro di tema) (deposito sistematico; retro-catalogo: tutte le voci di Wikipedia in francese, in ordine alfabetico).
Fonte: Wikipedia in francese, voce «Algorithme de Knuth-Morris-Pratt» — https://fr.wikipedia.org/wiki/Algorithme_de_Knuth-Morris-Pratt
Wikidata Q45285: «string searching algorithm» (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q45285
Autori: i contributori di Wikipedia (cronologia: https://fr.wikipedia.org/wiki/Algorithme_de_Knuth-Morris-Pratt?action=history).
Licenza: Creative Commons Attribuzione-Condividi allo stesso modo 4.0 (CC BY-SA 4.0) — https://creativecommons.org/licenses/by-sa/4.0/. Il riuso richiede attribuzione e stessa licenza.
Estratto dell'introduzione non modificato nel contenuto; revisione 238399387, consultata il 2026-10-17T11:14:28.950Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: bbed5d177cd39845ac7101dc5f6f05768834e4210c5a70f901cf0826be1214d5