Wyszukaj ciągi cykliczne

Question

Poszukuję najbardziej wydajnego sposobu na przechowywanie ciągów binarnych w strukturze danych (funkcja wstawiania), a następnie podczas pobierania łańcucha chcę sprawdzić, czy w strukturze znajduje się jakiś ciąg cykliczny danego ciągu.

Myślałem o przechowywaniu ciągów wejściowych w Trie, ale wtedy, gdy próbowałem ustalić, czy jakiś cykliczny ciąg ciągu, który teraz dostałem, został wstawiony do Trie znaczy zrobić | s | przeszukuje w Trie wszystkie możliwe ciągi cykliczne.

Czy istnieje sposób, aby zrobić to wydajniej, podczas gdy złożoność miejsca będzie jak w Trie?

Uwaga: Kiedy mówię cykliczne łańcuchy sznurku I oznacza, że ​​na przykład wszystkie cykliczne łańcuchy 1011 są: 0111, 1110, 1101, 1011

Answer 1

można wymyślić z funkcją canonicalizing dla cyklicznych ciągów w oparciu o następujące elementy:

1. Znajdź największy zera zer.
2. Obracaj ciąg znaków tak, aby liczba zer była z przodu.
3. Dla każdego przebiegu zer o jednakowym rozmiarze, zobacz, czy obracanie tego na przód tworzy leksykograficznie mniejszy ciąg, a jeśli tak, użyj go.

Byłoby to kanonicznej wszystko klasy równoważności (1011, 1101, 1110, 0111) do leksykograficznie najmniej wartość: 0111.

0101010101 jest drażliwy instancji, dla których ten algo nie wykona dobrze, ale jeśli twoje bity są z grubsza losowo rozmieszczone, to powinno dobrze działać w praktyce na długie struny.

Możesz wtedy mieszać w oparciu o formularz kanoniczny lub użyć trie, który będzie zawierał tylko pusty ciąg i ciągi, które zaczynają się od 0, a pojedynczy bieg trie odpowie na twoje pytanie.

EDIT:

jeśli mam ciąg o długości | S | znalezienie najmniejszej leksykograficznej wartości może zająć dużo czasu. Ile czasu zajmie to naprawdę?

Dlatego powiedziałem, że 010101.... jest wartością, dla której działa źle. Powiedzmy, że ciąg ma długość n, a najdłuższy bieg 1 jest długości r. Jeśli bity są losowo rozdzielone, długość najdłuższego przebiegu wynosi O (log n) zgodnie z "Distribution of longest run".

Czas znalezienia najdłuższego przebiegu to O (n). Możesz zaimplementować przełączanie za pomocą przesunięcia zamiast kopii bufora, która powinna być O (1). Liczba przebiegów jest najgorszym przypadkiem O (n/m).

Następnie czas, aby zrobić krok 3 powinny być

1. Znajdź innych dużych seriach: jedna O (n) przechodzi z O (log n) pamięci przeciętnego przypadku, O (n) najgorszy przypadek
2. Dla każdego uruchomienia: O (log n) przeciętny przypadek, O (n) najgorszy przypadek
3.   Przesunięcie i porównanie leksykograficzne: O (log n) średnia wielkość liter, ponieważ większość porównań losowo wybranych ciągów zawodzi wcześnie, O (n) najgorszy przypadek .

Prowadzi to do najgorszego przypadku O (n²), ale do przeciętnego przypadku O (n + log² n) ≅ O (n).

Answer 2

Masz n ciągów s1..sn i podajesz ciąg t chcesz wiedzieć, czy cykliczna permutacja t jest podłańcuchem dowolnego s1..sn. I chcesz przechowywać łańcuchy tak skutecznie, jak to możliwe. Czy poprawnie zrozumiałem twoje pytanie?

Jeśli tak, oto rozwiązanie, ale z dużym czasem działania: dla danego wejścia t, niech t '= concat (t, t), sprawdź t' z każdym s w s1..sn, aby zobaczyć jeśli najdłuższy podciąg t 'i sm wynosi co najmniej | t | Jeśli | si | = k, | t | = l działa w czasie O (n.k.l). I możesz przechowywać s1..sn w dowolnej strukturze danych, którą chcesz. Czy to wystarczająco dobre, czy ty?