| dbo:abstract
|
- In computer science, the longest repeated substring problem is the problem of finding the longest substring of a string that occurs at least twice. This problem can be solved in linear time and space by building a suffix tree for the string (with a special end-of-string symbol like '$' appended), and finding the deepest internal node in the tree with more than one child. Depth is measured by the number of characters traversed from the root. The string spelled by the edges from the root to such a node is a longest repeated substring. The problem of finding the longest substring with at least occurrences can be solved by first preprocessing the tree to count the number of leaf descendants for each internal node, and then finding the deepest node with at least leaf descendants. To avoid overlapping repeats, you can check that the list of suffix lengths has no consecutive elements with less than prefix-length difference. In the figure with the string "ATCGATCGA$", the longest substring that repeats at least twice is "ATCGA". (en)
- 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
|
- 1738 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| dbp:wikiPageUsesTemplate
| |
| dcterms:subject
| |
| rdf:type
| |
| rdfs:comment
|
- In computer science, the longest repeated substring problem is the problem of finding the longest substring of a string that occurs at least twice. This problem can be solved in linear time and space by building a suffix tree for the string (with a special end-of-string symbol like '$' appended), and finding the deepest internal node in the tree with more than one child. Depth is measured by the number of characters traversed from the root. The string spelled by the edges from the root to such a node is a longest repeated substring. The problem of finding the longest substring with at least occurrences can be solved by first preprocessing the tree to count the number of leaf descendants for each internal node, and then finding the deepest node with at least leaf descendants. To avoid ov (en)
- 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)
- Longest repeated substring problem (en)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:depiction
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageRedirects
of | |
| is dbo:wikiPageWikiLink
of | |
| is foaf:primaryTopic
of | |
