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).

algorithms optimization dynamic-programming strings subsequences 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

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

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

Odpowiedzi: