Najdłuższa powtarzająca się (rozproszona) sekwencja w ciągu

Nieformalne oświadczenie o problemie:

Biorąc pod uwagę ciąg znaków, np. $ACCABBAB$ , chcemy pokolorować niektóre litery na czerwono, a niektóre na niebiesko (a niektóre wcale), tak że czytanie tylko czerwonych liter od lewej do prawej daje taki sam wynik jak czytanie tylko niebieskie litery.

W przykładzie możemy je pokolorować w następujący sposób: $A\color{blue}{C}\color{red}{CAB}B\color{blue}{AB}$

Dlatego mówimy, że to powtarzająca się podsekwencja . Jest to również najdłuższy powtarzany podciąg (który można łatwo sprawdzić). $CAB$ $ACCABBAB$

Czy możemy efektywnie obliczyć najdłuższe powtarzające się podsekwencje?

Formalne pytanie:

Czy trudno jest NP zdecydować o łańcuchu i pewnym , czy w łańcuchu istnieje powtarzająca się podsekwencja długości ? $k$ $k$

Jeśli tak: Który problem można ograniczyć do tego problemu?
Jeśli nie: co to jest wydajny algorytm? (oczywiście tego algorytmu można następnie użyć do obliczenia najdłuższego powtarzanego podsekwencji)

Pytanie bonusowe:

Czy zawsze będą to powtarzające się podsekwencje długości $n/2 - o(n)$ jeśli rozmiar alfabetu jest ograniczony stałą?

(Wiadomo, że tak jest w przypadku alfabetów binarnych).

Edycja 2: Negatywna odpowiedź na pytanie bonusowe jest już znana dla alfabetów wielkości co najmniej $5$ . W rzeczywistości dla alfabetów o rozmiarze istnieją ciągi z najdłuższymi powtarzanymi podsekwencjami o długości zaledwie . Losowe ciągi wystarczy, aby to pokazać. Wynik już istniał, ale przeoczyłem go. $Σ$ $O(n · Σ^{-1/2})$

Edycja: Uwaga:

Niektóre osoby mają na myśli „podciąg”, gdy mówią „podciąg”. Ja nie. To nie jest problem ze znalezieniem podciągów dwukrotnie.

algorithms complexity-theory np-complete strings subsequences Sekti
źródło

Sekti, dziękuję. Masz rację: mój pierwszy komentarz był błędny; Teraz go usunąłem. Z drugiej strony, moja pozostałe komentarz jest mówić o nieciągłych podciągów. Jeśli

jest naprawione, istnieje sposób na rozwiązanie twojego problemu (z niesąsiadującymi podsekwencjami, które muszą być nienakładające się) w czasie

. Każdy podproblem dp śledzi indeksy wszystkich czerwonych liter i wszystkich wybranych do tej pory niebieskich liter. Jest to prawdopodobnie nieciekawe, ponieważ nie mówi nam, co się dzieje, gdy

jest częścią danych wejściowych.

k

$k$

O (n^{2 k + 2})

$O(n^{2k+2})$

k

$k$

@DW Dlaczego nie można skutecznie odpowiedzieć na pytanie formalne za pomocą tej modyfikacji najdłuższego wspólnego podsekwencji? Być może coś mi brakuje i ktoś może mi to wyjaśnić.

Bryce Kille

@BryceKille, nie wiem; może to może. Jeśli wymyślisz, jak to zrobić, mam nadzieję, że napiszesz odpowiedź!

Odpowiedzi:

-2

Można to rozwiązać w ~~czas wielomianowy~~przez skonstruowanie wykresu którym każdy węzeł reprezentuje punkt w niektórych powtarzanych podsekwencjach tak że . Krawędź między węzłami i oznacza, że można kontynuować przez tworząc powtarzające się podsekwencje o długości 2. $G$ $(i,j)$ $S$ $S[i]=S[j]$ $u$ $v$ $u$ $v$

1. Znajdź węzły. Można tego dokonać w czasie , budując posortowaną listę indeksów dla każdego znaku , a następnie wyliczając unikalne pary. Nie ma więcej niż węzłów. $O(n^2)$ $c$ $m=n^2$

2. Znajdź krawędzie. Potrzeba w celu sprawdzenia, czy węzeł może być kontynuowana przez węzeł , tak, rozważając wszystkie pary ten etap wykonuje czasu. $O(1)$ $u$ $v$ $(u,v)$ $O(m^2)$

3. Zauważ, że najdłuższa ścieżka w może nie być prawidłową powtarzaną podsekwencją. Rozważ ścieżki i . Jeśli istnieje krawędź to jest prawidłowym powtarzanym podsekwencją długości 3. Dlatego znalezienie wszystkich powtarzających się podsekwencji długości zajmuje . W ogólnym przypadku sprawdzenie, czy dwa prawidłowe ścieżki o długości można łączyć w prawidłową ścieżkę o długości . $G$ $ab$ $bc$ $ac$ $abc$ $O(m^4)$ $n$ $n+1$

4. Powtarzaj krok 3, aż nie będzie już można znaleźć ścieżek.

noplogist
źródło

Hmm Za szybko. W kroku 3 liczba podsekwencji do rozważenia staje się coraz większa. Więc to nie jest wielomian.

noplogist,

Witamy w CS.SE i dziękuję za próbę rozwiązania tego problemu! Obawiam się, że nie rozumiem twojego algorytmu. Co to jest krok 3? Wszystko, co widzę w „3.” są pewne deklaratywne stwierdzenia / obserwacje, ale nie widzę proceduralnej specyfikacji tego, co powinien zrobić algorytm. Nie rozumiem też, co to znaczy powtarzać krok 3, ani uzasadnienia twojego twierdzenia, że czas

wystarczający. Twój następny komentarz sprawia, że brzmi to tak, jakbyś już nie wierzył, że Twoja odpowiedź jest poprawna. Jeśli tak, lepiej usunąć odpowiedź, aby uniknąć nieporozumień.

O (n n m^{2})

$O(nnm^2)$

Zawsze możesz cofnąć usunięcie lub opublikować nową odpowiedź, jeśli później ją zorientujesz.

DW, dzięki. Dane wejściowe do kroku 3 to wszystkie powtarzające się podsekwencje o długości n, a dane wyjściowe to wszystkie powtarzane podsekwencje o długości n + 1. Uważam, że algorytm jest poprawny, ale nie jest algorytmem wielomianowym. Oznacziłem teraz twierdzenia, które uważam za nieprawidłowe.

noplogist,

Dziękuję Ci. Rozumiem. Niestety, przy tych poprawkach obawiam się, że ta odpowiedź nie odpowiada na zadane pytanie. Pytanie brzmiało: czy to NP-trudne? Czy istnieje skuteczny algorytm? Wykazanie, że istnieje algorytm czasu wykładniczego, nie pomaga w udzieleniu odpowiedzi na jedno z tych pytań. Rzeczywiście, już teraz jest banalnie łatwo dostrzec, że istnieje algorytm czasu wykładniczego dla tego problemu, bez przywoływania jakichkolwiek wymyślnych technik. Doceniam twoją próbę.