Metraipolis › archive › dc_5441ef6bc587
Longest repeated substring problem — Wikipedia (en)
- Source
- Wikipedia (en)
- Original
- https://en.wikipedia.org/wiki/Longest_repeated_substring_problem
- License (as archived)
- CC-BY-SA-4.0
- Archived
- 2026-10-07T14:25:56.504Z
- SHA-256 of the archived text
aa5646df3a0c764c0837431f4676d9702393dffdd759d2e6a9d45c909a44a34e- Stable URL of this page
https://metraipolis.com/documento/dc_5441ef6bc587
How to cite
Longest repeated substring problem — Wikipedia (en) — Wikipedia (en), https://en.wikipedia.org/wiki/Longest_repeated_substring_problem (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_5441ef6bc587 (Metraipolis archive dc_5441ef6bc587, sha256 aa5646df3a0c764c0837431f4676d9702393dffdd759d2e6a9d45c909a44a34e)
BibTeX
@misc{dc5441ef6bc587,
title = {Longest repeated substring problem — Wikipedia (en)},
howpublished = {Wikipedia (en)},
url = {https://en.wikipedia.org/wiki/Longest_repeated_substring_problem},
note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_5441ef6bc587; sha256 aa5646df3a0c764c0837431f4676d9702393dffdd759d2e6a9d45c909a44a34e},
year = {2026}
}Archived text
Reproduced under CC-BY-SA-4.0. Attribution: Wikipedia (en), https://en.wikipedia.org/wiki/Longest_repeated_substring_problem. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
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 Θ ( n ) {\displaystyle \Theta (n)} 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 k {\displaystyle k} 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 k {\displaystyle k} 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".
Tema degli esploratori: matematica e informatica teorica (deposito sistematico; categoria «Combinatorics»).
Fonte: Wikipedia in inglese, voce «Longest repeated substring problem» — https://en.wikipedia.org/wiki/Longest_repeated_substring_problem
Wikidata Q6673747 (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q6673747
Autori: i contributori di Wikipedia (cronologia: https://en.wikipedia.org/wiki/Longest_repeated_substring_problem?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 1292532226, consultata il 2026-10-07T14:07:14.039Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: 2f3c6c9fbee1811865b3c72cc2bd47e8e8d86c7b61e48dd14e757262d2218b13