Biorąc pod uwagę dwa ciągi , piszemy dla ich konkatenacji. Biorąc pod uwagę ciąg i liczba całkowita , napisać dla złączonych kopii . Teraz biorąc pod uwagę ciąg, możemy użyć tego zapisu do „skompresowania” go, tzn. można zapisać jako . Nazwijmy ten ciężar kompresji liczba znaków w niej występujących, więc waga jest dwa, a waga (a kompresja od ) jest trzy (oddzielny są liczone osobno).
Rozważmy teraz problem obliczania „najlżejszej” kompresji danego ciągu pomocą . Po pewnym namyśle istnieje oczywiste podejście do programowania dynamicznego, które działa w lub zależności od dokładnego podejścia.
Powiedziano mi jednak, że ten problem można rozwiązać w czasie , chociaż nie mogę znaleźć żadnych źródeł, jak to zrobić. W szczególności problem ten został podany w ostatnim konkursie programistycznym ( tutaj problem K , ostatnie dwie strony). Podczas analizy przedstawiono algorytm , a na końcu wspomniano o granicy pseudokwadratowej ( tutaj przy znaku czterominutowym). Niestety prezenter wspomniał tylko o „skomplikowanym słowie kombinatoryki”, więc teraz przyszedłem tutaj, aby poprosić o rozwiązanie :-)
źródło
Odpowiedzi:
Jeśli cię nie rozumiem, myślę, że minimalizację faktoryzacji kosztów można obliczyć w czasie w następujący sposób.O(n2)
Dla każdego indeksu i wiązkę wartości dla w następujący sposób. Niech będzie najmniejszą liczbą całkowitą, tak że istnieje liczba całkowita spełniającaDla tego konkretnego , niech będzie największym z tą właściwością. Jeśli nie ma takiego , ustaw , abyśmy wiedzieli, że dla tego indeksu istnieją wartości zerowe .(pℓi,rℓi) ℓ=1,2,… p1i≥1 r≥2 S[i−rp1i+1,i−p1i]=S[i−(r−1)p1i+1,i]. p1i r1i r pi Li=0 (pℓi,rℓi)
Niech będzie najmniejszą liczbą całkowitą ściśle większą niż spełniającą podobnie, dla niektórych . Tak jak poprzednio, weź za maksymalny z ustalonym . Ogólnie jest najmniejszą taką liczbą ściśle większą niż . Jeśli nie ma takiego , to .p2i (r1i−1)p1i S[i−r2ip2i+1,i−p2i]=S[i−(r2i−1)p2i+1,i] r2i≥2 r2i p2i pℓi (rℓ−1i−1)pℓ−1i pℓi Li=ℓ−1
Zauważ, że dla każdego indeksu i mamy powodu wzrostu wartości geometrycznie wraz z . (jeśli istnieje , to nie jest ono ściśle większe niż ale większe niż o co najmniej To określa wzrost geometryczny. )Li=O(log(i+1)) pℓi ℓ pℓ+1i (rℓi−1)pℓi pℓi/2
Zauważyliśmy już powyżej, że poprzez ograniczenie sumy warunek do terminu. Ale tak naprawdę, jeśli spojrzymy na całą sumę, możemy udowodnić coś ostrzejszego.∑jLj=O(∑jlog(j+1))=Θ(nlogn)
Rozważ drzewo sufiksów z tyłu (tj. Drzewo prefiksów S). każdą składkę sumą do krawędzi , aby każda krawędź została obciążona maksymalnie raz. Naładuj każdy do krawędzi emanującej z i idąc w kierunku . Tutaj jest liściem drzewa prefiksów odpowiadającego a nca oznacza najbliższego wspólnego przodka.T(S←) S ∑iLi T(S←) pji nca(v(i),v(i−pji)) v(i−pji) v(i) S[1..i]
To pokazuje, że . Wartości można obliczyć w czasie przez przejście do drzewa sufiksów, ale pozostawię szczegóły do późniejszej edycji, jeśli ktoś jest zainteresowany.O(∑iLi)=O(n) (pji,rji) O(n+∑iLi)
Daj mi znać, jeśli to ma sens.
źródło
Jest twój początkowy ciąg S o długości n. Oto pseudo-kod metody.
Celowo podałem trochę szczegółów na temat „nawiasów końcowych”, ponieważ wymaga to wielu kroków do układania w stosy i rozpakowywania, co pozwoliłoby na wyjaśnienie podstawowej metody. Chodzi o to, aby przetestować ewentualny dalszy skurcz wewnątrz pierwszego. na przykład ABCBCABCBC => (ABCBC) ² => (A (BC) ²) ².
Dlatego głównym celem jest poszukiwanie dużych okresów w pierwszej kolejności. Zauważ, że S [i] jest i-tym określeniem S pomijającym dowolne „(”, „)” lub moc.
Jest to globalnie O (n²log (n)).
źródło