Szukam struktury danych, która przechowuje zestaw ciągów znaków nad zestawem znaków , zdolną do wykonywania następujących operacji. Oznaczmy D ( S ) , jak w strukturze danych przechowującej zestaw łańcuchy S .$\Sigma$$\mathcal{D}(S)$$S$

• Add-Prefix-Setna : biorąc pod uwagę pewien zestaw T (prawdopodobnie pustych) ciągów, których rozmiar jest ograniczony stałą, a których długości są ograniczone stałą, zwraca D ( { t s | t ∈ T , s ∈ S } ) . Oba te stałe ograniczające są globalne: są takie same dla wszystkich wejść T .$\mathcal{D}(S)$$T$$\mathcal{D}( \{ t s\ |\ t \in T, s \in S\} )$$T$
• Get-Prefixesna : return { a | a s ∈ S , a ∈ Σ } . Zauważ, że tak naprawdę nie przeszkadza mi, jaka struktura jest używana dla tego zestawu, o ile mogę wyliczyć jego zawartość w czasie O ( | Σ | ) .$\mathcal{D}(S)$$\{ a \ | \ as \in S, a \in \Sigma \}$$O(|\Sigma|)$
• Remove-Prefixesna : zwraca D ( { s | a s ∈ S , a ∈ Σ } ) .$\mathcal{D}(S)$$\mathcal{D}( \{ s \ | \ as \in S, a \in \Sigma \} )$
• Merge: biorąc pod uwagę i D ( T ) , zwróć D ( S ∪ T ) .$\mathcal{D}(S)$$\mathcal{D}(T)$$\mathcal{D}(S \cup T)$

Teraz naprawdę chciałbym wykonać wszystkie te operacje w czasie , ale dobrze mi jest ze strukturą, która wykonuje wszystkie te operacje w czasie o ( n ) , gdzie n jest długością najdłuższego ciągu w Struktura. W przypadku scalania Chciałbym O ( n 1 + n 2 ) czas trwania, w którym n 1 jest brak w pierwszym i n 2 N dla drugiej struktury.$O(1)$$o(n)$$n$$o(n_1+n_2)$$n_1$$n$$n_2$$n$

Dodatkowym wymaganiem jest to, że struktura jest niezmienna lub przynajmniej, że powyższe operacje zwracają „nowe” struktury, tak aby wskaźniki do starych nadal działały jak poprzednio.

Uwaga na temat amortyzacji: w porządku, ale musisz uważać na wytrwałość. Ponieważ cały czas ponownie używam starych struktur, będę miał kłopoty, jeśli trafię w najgorszy przypadek jakimś określonym zestawem operacji na tej samej strukturze (ignorując nowe struktury, które tworzy).

Chciałbym użyć takiej struktury w algorytmie analizującym, nad którym pracuję; powyższa struktura zawiera oczekiwany przeze mnie algorytm.

Już rozważałem użycie trie , ale głównym problemem jest to, że nie wiem, jak skutecznie połączyć próby. Jeśli zestaw ciągów znaków Add-Prefix-Setskłada się tylko z ciągów jednoznakowych, możesz przechowywać te zestawy w stosie, co dałoby ci czas uruchamiania dla pierwszych trzech operacji. Jednak to podejście nie działa również w przypadku łączenia.$O(1)$

Na koniec zauważ, że nie interesują mnie czynniki : to jest stałe dla wszystkich mnie obchodzi.$|\Sigma|$

Myślałem od dłuższego czasu, ale nie znalazłem problemu z wykonaniem wszystkich operacji w najgłupszy możliwy sposób w strukturze DAG przypominającej trie:

Dodaj zestaw prefiksów

$T$

$O(|T|)$

Łączyć

Połącz korzenie dwóch struktur: utwórz wszystkie węzły potomne drugiego korzenia potomnego pierwszego węzła. Możesz teraz mieć wiele krawędzi oznaczonych tym samym znakiem z tego samego węzła.

$O(1)$

Leniwa aktualizacja katalogu głównego

1. $O(|\Sigma|)$$O(1)$
2. $O(1)$

Uzyskaj prefiksy

Leniwa aktualizacja katalogu głównego. Teraz znajdź wszystkie dzieci roota i zgłoś do nich zestaw liter na krawędziach.

$O(|\Sigma|)$

Usuń prefiksy

Leniwa aktualizacja katalogu głównego. Zjednocz wszystkie dzieci roota i ustaw wskaźnik root na wynik tego połączenia. Leniwa aktualizacja nowego katalogu głównego.

$O(|\Sigma|)$

Trwałość

$O(1)$$O(|\Sigma|)$$O(log N)$$N$