| Property |
Value |
| dbo:abstract
|
- 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), permettant de trouver les occurrences d'une chaîne dans un texte avec une complexité linéaire dans le pire cas. 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. L'algorithme a été conçu en 1970 par Knuth et (en), et dans un autre contexte, par (en), 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, en étudiant un problème de reconnaissance d'occurrence de chaîne. (fr)
- 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), permettant de trouver les occurrences d'une chaîne dans un texte avec une complexité linéaire dans le pire cas. 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. L'algorithme a été conçu en 1970 par Knuth et (en), et dans un autre contexte, par (en), 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, en étudiant un problème de reconnaissance d'occurrence de chaîne. (fr)
|
| dbo:discoverer
| |
| dbo:namedAfter
| |
| dbo:wikiPageExternalLink
| |
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 29311 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| prop-fr:année
|
- 1971 (xsd:integer)
- 1973 (xsd:integer)
- 1977 (xsd:integer)
|
| prop-fr:auteur
|
- David Eppstein (fr)
- J Strother Moore (fr)
- Olivier Carton (fr)
- David Eppstein (fr)
- J Strother Moore (fr)
- Olivier Carton (fr)
|
| prop-fr:fr
|
- James H. Morris (fr)
- Vaughan Pratt (fr)
- James H. Morris (fr)
- Vaughan Pratt (fr)
|
| prop-fr:lang
| |
| prop-fr:langue
|
- en (fr)
- fr (fr)
- ru (fr)
- en (fr)
- fr (fr)
- ru (fr)
|
| prop-fr:lienAuteur
|
- Donald Knuth (fr)
- James H. Morris, Jr. (fr)
- Vaughan Pratt (fr)
- Donald Knuth (fr)
- James H. Morris, Jr. (fr)
- Vaughan Pratt (fr)
|
| prop-fr:lireEnLigne
| |
| prop-fr:nom
|
- Knuth (fr)
- Maiyasevich (fr)
- Morris Jr. (fr)
- Pratt (fr)
- Матиясевич (fr)
- Knuth (fr)
- Maiyasevich (fr)
- Morris Jr. (fr)
- Pratt (fr)
- Матиясевич (fr)
|
| prop-fr:numéro
| |
| prop-fr:page
|
- 64 (xsd:integer)
- 104 (xsd:integer)
|
| prop-fr:pages
| |
| prop-fr:prénom
|
- Vaughan (fr)
- Yuri (fr)
- Donald (fr)
- James H. (fr)
- Юрий (fr)
- Vaughan (fr)
- Yuri (fr)
- Donald (fr)
- James H. (fr)
- Юрий (fr)
|
| prop-fr:périodique
|
- Journal of Soviet Mathematics (fr)
- SIAM Journal on Computing (fr)
- Записки научных семинаров Ленинградского отделения Математического института им. В.А.Стеклова (fr)
- Journal of Soviet Mathematics (fr)
- SIAM Journal on Computing (fr)
- Записки научных семинаров Ленинградского отделения Математического института им. В.А.Стеклова (fr)
|
| prop-fr:site
|
- CS (fr)
- ICS (fr)
- LIAFA (fr)
- CS (fr)
- ICS (fr)
- LIAFA (fr)
|
| prop-fr:texte
|
- Morris (fr)
- Pratt (fr)
- Morris (fr)
- Pratt (fr)
|
| prop-fr:titre
|
- Algorithmes de Knuth, Morris et Pratt (fr)
- Fast pattern matching in strings (fr)
- О распознавании в реальное время отношения вхождения (fr)
- KPM example (fr)
- Knuth-Morris-Pratt string matching (fr)
- Real-time recognition of the inclusion relation (fr)
- Algorithmes de Knuth, Morris et Pratt (fr)
- Fast pattern matching in strings (fr)
- О распознавании в реальное время отношения вхождения (fr)
- KPM example (fr)
- Knuth-Morris-Pratt string matching (fr)
- Real-time recognition of the inclusion relation (fr)
|
| prop-fr:trad
|
- James H. Morris (fr)
- Vaughan Pratt (fr)
- James H. Morris (fr)
- Vaughan Pratt (fr)
|
| prop-fr:url
| |
| prop-fr:volume
|
- 1 (xsd:integer)
- 6 (xsd:integer)
- 20 (xsd:integer)
|
| prop-fr:wikiPageUsesTemplate
| |
| dct:subject
| |
| rdfs:comment
|
- 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), permettant de trouver les occurrences d'une chaîne dans un texte avec une complexité linéaire dans le pire cas. 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. (fr)
- 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), permettant de trouver les occurrences d'une chaîne dans un texte avec une complexité linéaire dans le pire cas. 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. (fr)
|
| rdfs:label
|
- Algorithme de Knuth-Morris-Pratt (fr)
- Knuth–Morris–Pratt algorithm (en)
- Thuật toán Knuth–Morris–Pratt (vi)
- Алгоритм Кнута — Морріса — Пратта (uk)
- Алгоритм Кнута — Морриса — Пратта (ru)
- クヌース–モリス–プラット法 (ja)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageRedirects
of | |
| is dbo:wikiPageWikiLink
of | |
| is oa:hasTarget
of | |
| is foaf:primaryTopic
of | |
