Nejdelší opakovaný problém s podřetězcem - Longest repeated substring problem - Wikipedia

Strom přípon písmen ATCGATCGA $

v počítačová věda, nejdelší opakovaný problém s podřetězcem je problém najít nejdelší podřetězec a tětiva který se vyskytuje nejméně dvakrát.

Tento problém lze vyřešit v lineárním čase a prostoru ${ displaystyle Theta (n)}$ stavbou a příponový strom pro řetězec (se zvláštním symbolem konce řetězce, jako je '$') a nalezení nejhlubšího vnitřního uzlu ve stromu. Hloubka se měří počtem znaků procházejících z kořene. Řetězec hláskovaný hranami od kořene k takovému uzlu je nejdelší opakovaný podřetězec. Problém s nalezením nejdelšího podřetězce ${ displaystyle k}$ výskyty lze vyřešit nejprve předběžným zpracováním stromu, aby se spočítal počet potomků listů pro každý vnitřní uzel, a poté vyhledáním nejhlubšího uzlu s alespoň ${ displaystyle k}$ potomci listů, kteří nemají žádné děti. Abyste se vyhnuli překrývajícímu se opakování, můžete zkontrolovat, zda seznam délek přípon nemá žádné po sobě jdoucí prvky s rozdílem délek než prefixů.

Na obrázku s řetězcem „ATCGATCGA $“ je nejdelší podřetězec, který se opakuje alespoň dvakrát, „ATCGA“.

externí odkazy

• Allison, L. "Příponové stromy". Citováno 2008-10-14.
• C implementace nejdelšího opakovaného podřetězce pomocí Suffix Tree
• Online demo: Nejdelší opakovaný podřetězec

Tento algoritmy nebo datové struktury související článek je a pahýl. Wikipedii můžete pomoci pomocí rozšiřovat to.