| Property |
Value |
| dbo:abstract
|
- En informatique, le problème de la plus longue sous-chaîne répétée est le problème de recherche de la plus longue sous-chaîne d'une chaîne qui y apparaît au moins deux fois. Par exemple, la plus longue sous-chaîne dans « GEEKSFORGEEKS » est « GEEKS », dans « AAAA » est « AAA », dans « ATCGATCGA » est « ATCGA ».Le problème peut être résolu en temps linéaire et en espace par la construction d'un arbre des suffixes de la chaîne. On cherche le nœud interne le plus profond interne dans l'arbre qui a au moins deux feuilles parmi ses descendants. La profondeur est mesurée par le nombre de caractères traversées à partir de la racine. La chaîne qui étiquette les arcs de la racine à un tel nœud est une plus longue sous-chaîne répétée. Dans la figure ci-contre, l'arbre des suffixes de la chaîne « ATCGATCGA$ ». La plus longue sous-chaîne répétée au moins deux fois est « ATCGA ». Dans l'arbre, le nœud le plus profond (tous ont deux feuilles parmi leurs descendants) est celui portant le numéro 2. Sa profondeur est 5, longueur de la chaîne « ATCGA ». (fr)
- En informatique, le problème de la plus longue sous-chaîne répétée est le problème de recherche de la plus longue sous-chaîne d'une chaîne qui y apparaît au moins deux fois. Par exemple, la plus longue sous-chaîne dans « GEEKSFORGEEKS » est « GEEKS », dans « AAAA » est « AAA », dans « ATCGATCGA » est « ATCGA ».Le problème peut être résolu en temps linéaire et en espace par la construction d'un arbre des suffixes de la chaîne. On cherche le nœud interne le plus profond interne dans l'arbre qui a au moins deux feuilles parmi ses descendants. La profondeur est mesurée par le nombre de caractères traversées à partir de la racine. La chaîne qui étiquette les arcs de la racine à un tel nœud est une plus longue sous-chaîne répétée. Dans la figure ci-contre, l'arbre des suffixes de la chaîne « ATCGATCGA$ ». La plus longue sous-chaîne répétée au moins deux fois est « ATCGA ». Dans l'arbre, le nœud le plus profond (tous ont deux feuilles parmi leurs descendants) est celui portant le numéro 2. Sa profondeur est 5, longueur de la chaîne « ATCGA ». (fr)
|
| dbo:thumbnail
| |
| dbo:wikiPageExternalLink
| |
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 2298 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| prop-fr:auteur
|
- Robert Sedgewick and Kevin Wayne (fr)
- Robert Sedgewick and Kevin Wayne (fr)
|
| prop-fr:consultéLe
| |
| prop-fr:nom
|
- Allison (fr)
- Allison (fr)
|
| prop-fr:prénom
| |
| prop-fr:site
| |
| prop-fr:série
|
- Introduction to Programming in Java, Section 4.2: Searching and Sorting (fr)
- Introduction to Programming in Java, Section 4.2: Searching and Sorting (fr)
|
| prop-fr:titre
|
- Longest repeated substring (fr)
- Suffix Tree Application 3 – Longest Repeated Substring (fr)
- Longest repeated substring (fr)
- Suffix Tree Application 3 – Longest Repeated Substring (fr)
|
| prop-fr:url
| |
| prop-fr:wikiPageUsesTemplate
| |
| prop-fr:éditeur
|
- Faculty of Information Technology, Monash University, Australie (fr)
- Faculty of Information Technology, Monash University, Australie (fr)
|
| dct:subject
| |
| rdfs:comment
|
- En informatique, le problème de la plus longue sous-chaîne répétée est le problème de recherche de la plus longue sous-chaîne d'une chaîne qui y apparaît au moins deux fois. Par exemple, la plus longue sous-chaîne dans « GEEKSFORGEEKS » est « GEEKS », dans « AAAA » est « AAA », dans « ATCGATCGA » est « ATCGA ».Le problème peut être résolu en temps linéaire et en espace par la construction d'un arbre des suffixes de la chaîne. On cherche le nœud interne le plus profond interne dans l'arbre qui a au moins deux feuilles parmi ses descendants. La profondeur est mesurée par le nombre de caractères traversées à partir de la racine. La chaîne qui étiquette les arcs de la racine à un tel nœud est une plus longue sous-chaîne répétée. (fr)
- En informatique, le problème de la plus longue sous-chaîne répétée est le problème de recherche de la plus longue sous-chaîne d'une chaîne qui y apparaît au moins deux fois. Par exemple, la plus longue sous-chaîne dans « GEEKSFORGEEKS » est « GEEKS », dans « AAAA » est « AAA », dans « ATCGATCGA » est « ATCGA ».Le problème peut être résolu en temps linéaire et en espace par la construction d'un arbre des suffixes de la chaîne. On cherche le nœud interne le plus profond interne dans l'arbre qui a au moins deux feuilles parmi ses descendants. La profondeur est mesurée par le nombre de caractères traversées à partir de la racine. La chaîne qui étiquette les arcs de la racine à un tel nœud est une plus longue sous-chaîne répétée. (fr)
|
| rdfs:label
|
- Plus longue sous-chaîne répétée (fr)
- Plus longue sous-chaîne répétée (fr)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:depiction
| |
| foaf:homepage
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageWikiLink
of | |
| is oa:hasTarget
of | |
| is foaf:primaryTopic
of | |
