Znajdowanie najdłuższego powtarzającego się podsekwencji

Biorąc pod uwagę ciąg $s$ , Chciałbym znaleźć najdłuższą powtarzającą się (przynajmniej dwukrotnie) podsekwencję. To znaczy, chciałbym znaleźć ciąg $w$ który jest podciągiem (nie musi być ciągły) z $s$ takie, że $w=w' \cdot w'$ . To jest, $w$ to ciąg, którego połówki pojawiają się dwa razy z rzędu. Zauważ, że $w$ jest podsekwencją $s$ , ale niekoniecznie podłańcuch.

Przykłady:

W przypadku „ababccabdc” będzie to „abcabc”, ponieważ „abc” = „abc” i „abc” pojawia się (przynajmniej) dwa razy w „ababccabdc”.

W przypadku „addbacddabcd” jedną z opcji jest „dddd”, ponieważ „dd” pojawia się dwukrotnie (nie mogę użyć tej samej litery kilka razy, ale tutaj mam 4 'd, więc jest w porządku), ale ma siłę 4. Mogę znaleźć lepszą o długości 8: „abcdabcd”, ponieważ „abcd” jest podciągiem „addbacddabcd”, który pojawia się dwukrotnie.

Jestem zainteresowany znalezieniem najdłuższego powtarzającego się podciągu. Nazywa się to również „znajdowaniem najdłuższego / największego kwadratu”, ale przeczytałem wiele artykułów, w których kwadrat jest zdefiniowany dla podłańcucha, a nie podsekwencji.

Mogę łatwo użyć algorytmu brutalnej siły, który zajmie $O(n^3)$ poprzez iterację wszystkich opcji punktu przerwania w ciągu, a następnie będę mieć dwa ciągi, w których będę szukał największej / najdłuższej wspólnej podsekwencji, ale każde sprawdzenie zajmie $O(n^2)$ za pomocą techniki programowania dynamicznego, więc cały czas będzie $O(n^3)$ . Znalazłem bardziej wydajny algorytm dla najdłuższego wspólnego podciągu, który zajmuje $O(\frac{n^2}{\log n})$ , więc będzie czas pracy $O(\frac{n^3}{\log n})$ .

Szukam bardziej wydajnego algorytmu dla najdłuższego powtarzającego się problemu z podsekwencją. Być może mój pomysł iteracji po wszystkich punktach przerwania marnuje zbyt dużo czasu i może zostać zredukowany do mniejszej liczby iteracji. A może algorytm o innym podejściu może rozwiązać ten problem.

Szukałem w wielu czasopismach i poprzednich pytaniach, a większość wyników, które znalazłem, dotyczyły podciągów, a nie podsekwencji.

Czytałem również, że można to zrobić za pomocą drzewek sufiksów, ale to również dotyczyło podłańcuchów i nie jestem pewien, czy taki pomysł można rozszerzyć na podsekwencje.

Szukam rozwiązania, które działa na czas $O(n^2)$ . Jeśli istnieje jeden na czas $O(n \cdot \log n)$ będzie jeszcze lepiej (nie jestem pewien, czy takie istnieje).

— Dan D-man
źródło

Wyszukaj drzewa przyrostków lub tablice przyrostków.

— pseudonim

Jest bardzo mało prawdopodobne, że

o (n^{2})

$o(n^2)$ dla tego problemu istnieje algorytm czasu, ponieważ gdyby tak się stało, można go użyć do pokonania najbardziej znanego algorytmu znajdowania LCS o dwóch długościach

n

$n$ smyczki

u

$u$ i

v

$v$ w następujący sposób: Utwórz ciąg

x u x v

$xuxv$ , gdzie

x

$x$ jest

n + 1

$n+1$ kopie znaku $, który nie pojawia się w żadnym z nich

u

$u$ lub

v

$v$ , a następnie uruchom swój

o (n^{2})

$o(n^2)$ algorytm czasu na nim. Obie „połówki” najdłuższego powtarzającego się podsekwencji na pewno się zaczną

x

$x$ , więc połowa pochodzi z każdego z nich

u

$u$ i

v

$v$ , rozwiązując problem LCS.

— j_random_hacker

@j_random_hacker LCS można rozwiązać

O (n + m)

$\mathcal O(n+m)$ używając drzewa sufiksów lub w

O (n \log n)

$\mathcal O(n\log n)$ za pomocą skrótów.

— Zły

@Evil: Nie wiem jeszcze, jak mógłbyś podać trochę więcej szczegółów? (Czy na pewno nie myślisz o najdłuższym wspólnym łańcuchu podrzędnym , który można rozwiązać w tych zawiłościach czasowych?)

— j_random_hacker

@j_random_hacker Myślałem, że porównujesz cel

o (n^{2})

$o(n^2)$ z LCS (kolejne), ale tutaj, jak wspomniałeś, tak, nawet nie widziałem działającego rozwiązania w n ^ 2 dla najdłuższej wspólnej sekwencji (znalazłem jeden dynamiczny kod programowania, propagowany na wielu stronach, który jest wadliwy, podobny do negatywnej odpowiedzi). Przepraszam, po prostu źle zrozumiałem twój komentarz.

— Zły

-1

Oto rozwiązanie do programowania dynamicznego.

Załóżmy, że ciąg wejściowy to $x_1\ldots x_n$ . Utwórz tabelę $T$ których wiersze i kolumny są indeksowane $0,\ldots,n$ (gdzie $n$ jest długością ciągu), wypełnianą przez regułę

T [i, j] = {\begin{cases} 0 & if i = 0 or j = 0, \\ T [i - 1, j - 1] + 1 & if x_{i} = x_{j} and i \neq j, \\ max (T [i - 1, j], T [i, j - 1]) & otherwise . \end{cases}

$T[i,j] = \begin{cases} 0 & \text{if $i = 0$ or $j = 0$}, \\ T[i-1,j-1] + 1 & \text{if $x_i = x_j$ and $i \neq j$}, \\ \max(T[i-1,j],T[i,j-1]) & \text{otherwise}. \end{cases}$ Odpowiedź brzmi .

T [n, n]

$T[n,n]$

— jir17
źródło

Załóżmy, że mamy jakieś z , a warunek w Twojej instrukcji jest prawdziwy. Następnie zakłada, że postać w pozycji jest częścią obu podciągów.

i, j

$i, j$

i = j + 1

$i=j+1$ ifdp[i][j] = dp[i - 1][j - 1] + 1

i - 1 = j

$i-1=j$

— j_random_hacker

Witamy w informatyce! Pozbądź się kodu źródłowego i zastąp go pomysłami, pseudo kodem i argumentami poprawności. Zobacz tutaj i tutaj, aby uzyskać powiązane dyskusje na temat meta.

— Raphael

@Raphael Formuła rekurencyjna nie jest liczona jako kod źródłowy.

— Number945

@BreakingBenjamin W zależności od wybranego języka możesz zapisać dane powtórzenie mniej więcej dosłownie. Chodzi o to, że nie ma tutaj żadnego wyjaśnienia.

— Raphael