Problem z najdłuższym powtarzającym się podłańcuchem

Drzewo sufiksów liter ATCGATCGA$

W informatyce problem z najdłuższym powtarzającym się podłańcuchem polega na znalezieniu najdłuższego podłańcucha , który występuje co najmniej dwa razy.

Ten problem można rozwiązać w liniowym czasie i przestrzeni , budując drzewo sufiksów dla łańcucha (ze specjalnym symbolem końca łańcucha, takim jak „$”) i znalezieniem Θ ( n ) {\ Displaystyle \ $($ najgłębszy wewnętrzny węzeł w drzewie z więcej niż jednym dzieckiem. Głębokość jest mierzona liczbą znaków przechodzących od korzenia. Łańcuch pisany przez krawędzie od korzenia do takiego węzła jest najdłuższym powtarzającym się podłańcuchem. Problem ze znalezieniem najdłuższego podciągu z co najmniej ${\ displaystyle k}$$, najpierw przetwarzając$ w celu policzenia liczby potomków liści dla każdego węzła wewnętrznego, a następnie znajdując najgłębszy węzeł z co najmniej potomkami liści. Aby uniknąć nakładających się powtórzeń, możesz sprawdzić, czy na liście długości sufiksów nie ma kolejnych elementów, których różnica długości jest mniejsza niż różnica długości prefiksu.

Na rysunku z łańcuchem „ATCGATCGA$” najdłuższym podciągiem, który powtarza się co najmniej dwukrotnie, jest „ATCGA”.

Linki zewnętrzne

• Allison, L. „Drzewa sufiksów” . Źródło 2008-10-14 .
• Implementacja C najdłuższego powtarzanego podciągu przy użyciu drzewa sufiksów
• Demo online: najdłuższy powtarzający się podciąg