Longest repeated substring problem
id:
longest-repeated-substring-problem-245-5918912
title:
Longest repeated substring problem
text:
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, 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
brand slug:
wiki
category slug:
encyclopedia
description:
original url:
https://en.wikipedia.org/wiki/Longest_repeated_substring_problem
date created:
date modified:
2023-08-11T17:25:07Z
main entity:
{"identifier":"Q6673747","url":"https://www.wikidata.org/entity/Q6673747"}
image:
{"content_url":"https://upload.wikimedia.org/wikipedia/commons/d/dd/ATCGATCGA%24_Suffix_Tree.png","width":1080,"height":645}
fields total:
13
integrity:
14