Biorąc pod uwagę n ciągów, czy jeden z nich jest podciągiem innego?

Załóżmy, że otrzymaliśmy zbiór ciągów, . Chciałbym wiedzieć, czy którykolwiek z tych ciągów jest podciągiem dowolnego innego ciągu w kolekcji. Innymi słowy, chciałbym algorytm dla następującego zadania: $n$ $S_1,\dots,S_n$

Dane wejściowe: $S_1,\dots,S_n$

Wyjście: takie, że jest podłańcuchem i , lub None, jeśli nie takie exist $i,j$ $S_i$ $S_j$ $i\ne j$ $i,j$

Czy istnieje na to wydajny algorytm?

Jeśli zamienimy „podłańcuch” na „przedrostek”, istnieje skuteczny algorytm (posortuj ciągi, a następnie wykonaj skanowanie liniowe, aby porównać sąsiednie ciągi; sortowanie zapewni, że podciągi są sąsiadujące). Ale trudniejsze wydaje się sprawdzenie, czy dowolny ciąg znaków jest podciągiem dowolnego innego ciągu. Naiwny algorytm polega na iteracji wszystkich par , ale wymaga to testów podciągowych . Czy istnieje bardziej wydajny algorytm? $i,j$ $\Theta(n^2)$

Myślę, że moglibyśmy nazwać to „testowaniem podciągów na wszystkich parach” lub coś w tym rodzaju.

Moim ostatecznym celem jest przycięcie kolekcji, aby żaden ciąg nie był podciągiem innych elementów, poprzez usunięcie każdego z nich, który jest podciągiem czegoś innego w kolekcji.

Wskazówka: tablica sufiksów.

pseudonim

Na marginesie, nie jest poprawne, jeśli usuniesz podciągi, gdy je znajdziesz. Będzie mniej. Ponadto należy sortować według długości, ponieważ dłuższy ciąg nie może pojawić się w krótszym ciągu. Znowu jest tutaj źle.

Θ (n^{2})

$\Theta(n^2)$

Θ (n^{2})

$\Theta(n^2)$

Alexis Wilke,

@AlexisWilke, jest poprawna: taka jest liczba testów podłańcuchowych w najgorszym przypadku (najgorszy przypadek to taki, że żaden ciąg nie jest podciągiem innym). Sortowanie według długości daje tylko współczynnik dwa, co nie wpływa na asymptotyki.

Θ (n^{2})

$\Theta(n^2)$

Odpowiedzi:

Możesz zbudować drzewo sufiksów w czasie liniowym i sprawdzić, czy istnieje wewnętrzny węzeł, który odpowiada pełnemu ciągowi (stały czas na węzeł).

Bardziej szczegółowo załóżmy, że otrzymujemy ciągi . $s_1, \dots, s_n \in \Sigma^*$

Budowanie (uogólnionego) drzewa sufiks z o parami różne znaczniki zaciskowe . $s_1\$_1, s_2\$_2, \dots, s_n\$_n$ $n$ $\$_1,\dots,\$_n \notin \Sigma$

Za pomocą algorytmu Ukkonen można to zrobić w czasie liniowym; liniowy w sumie wszystkich długości łańcucha.
Zakładając, że etykieta liście z , jeżeli stanowią one przyrostek z , przemierzać drzewo i znaleźć te liście oznaczonych , czyli liści, które odpowiadają w pełni smyczki. $(i,j)$ $s_i[j..|s_i|]$ $s_i$ $n$ $(i,0)$

To zajmuje czas liniowy w rozmiarze drzewa, który sam jest liniowy w rozmiarze wejściowym.
Liście potomne elementu nadrzędnego (do którego prowadzi krawędź oznaczona ) reprezentują wszystkie dopasowania z zestawu; wynika to z podstawowego niezmiennika drzewek sufiksów. Znajdź dowolne dopasowanie, schodząc do dowolnego liścia (ale ). $(i,0)$ $\$_i$ $(i,0)$

To znowu zajmuje czas liniowy.

Oddzielne znaczniki końcowe nie są tak naprawdę konieczne; jeden używany do zakończenia wszystkich ciągów jest wystarczający, o ile pozwala się na wiele etykiet na liść.

Raphael
źródło