Oblicz przebiegi ciągu

Rozważ następujące definicje zaczerpnięte z liczby przebiegów w ciągu W. Ryttera. Zauważ, że słowo, ciąg i podciąg są z grubsza synonimami.

Przebieg w ciągu to nieściągalny (z tym samym minimalnym okresem) okresowy odcinek w ciągu.

Okres p słowa w jest dowolną liczbą całkowitą dodatnią p, tak że w [i] = w [i + p], ilekroć zdefiniowane są obie strony tego równania. Niech na (w) oznacza wielkość najmniejszego okresu w. Mówimy, że słowo w jest okresowym iff na (w) <= | w | / 2.

Na przykład rozważ ciąg x = abcab. per(abcab) = 3jak x[1] = x[1+3] = a, x[2]=x[2+3] = bi nie ma mniejszy okres. Łańcuch nie abcabjest zatem okresowy. Jednak ciąg ababjest okresowy zgodnie z (abab) = 2.

Przebieg (lub maksymalna okresowość) w ciągu w to przedział [i ... j] zj> = i, taki że

w [i ... j] to słowo okresowe z kropką p = na (w [i ... j])
Jest maksymalny. Formalnie ani w [i-1] = w [i-1 + p], ani w [j + 1] = w [j + 1-p]. Nieoficjalnie przebieg nie może być zawarty w większym przebiegu z tym samym okresem.

Oznacz przez RUNS (w) zestaw przebiegów w.

Przykłady

Cztery przebiegi atattattto [4,5] = tt, [7,8] = tt, [1,4] = atat, [2,8] = tatt.

Ciąg aabaabaaaacaacaczawiera następujące 7 przebiegów:

[1,2] = aa, [4,5] = aa, [7,10] = aaaa, [12,13] = aa, [13,16] = acac, [1,8] = aabaabaa, [9 , 15] = aacaaca.

Twój wynik powinien być listą przebiegów. Każde uruchomienie powinno określać interwał, który reprezentuje, ale nie musi generować samego podłańcucha. Dokładne formatowanie może być dla Ciebie wygodne.

Przykłady używają indeksowania 1, ale zamiast tego możesz swobodnie korzystać z indeksowania 0, jeśli jest to wygodniejsze.

ZADANIE

Napisz kod o podanym łańcuchu w, wypisz RUNS (w).

Języki i wprowadzanie

Możesz użyć dowolnego języka, który ci się podoba, i pobrać ciąg wejściowy w dowolnej dogodnej formie. Musisz jednak podać pełny program i powinieneś pokazać przykład swojego kodu działającego na przykładowym wejściu.

code-golf string

Niezłe wyzwanie, ale czy istnieje dobry powód, aby przesłonić ustawienia domyślne i zabronić funkcji?

— Martin Ender

@MartinEnder To tylko moje preferencje. Ułatwia to ludziom kopiowanie i wklejanie kodu oraz wypróbowywanie go, co z kolei sprawia, że odpowiedzi są bardziej interesujące dla większej liczby osób.

Powoduje to jednak również znaczne nakładanie się kodu, co powoduje, że konkurencja jest niesprawiedliwa dla języków z pełną składnią. Na przykład nie grałbym w golfa w Javie, gdybym musiał pisać class A{public static ...}za każdym razem, gdy chciałem grać w golfa

— Bassdrop Cumberwubwubwub,

@BassdropCumberwubwubwub Widzę, że są plusy i minusy. Zdarza mi się mocniej ważyć profesjonalistów. Wydaje mi się, że najbardziej interesujące jest porównanie długości odpowiedzi golfowych w podobnych językach, zamiast porównywania APL z Pythonem na przykład.

„przebieg jest maksymalny, jeśli nie jest w pełni zawarty w żadnym większym przebiegu”, ale w twoim pierwszym przykładzie [7,8] jest całkowicie zawarty w [2,8]. A może mówisz ściśle o przebiegach, które powtarzają ten sam podciąg?

— Aditsu zakończyło się, ponieważ SE to EVIL

Odpowiedzi:

Pyth, 38 bajtów

{smm,hk+ekdfgaFTdcx1xM.ttB+0qVQ>QdZ2Sl

  m                                 SlQ   map for d in [1, …, len(input)]:
                            qVQ>Qd          pairwise equality of input[:-d] and input[d:]
                        tB+0                duplicate this list, prepending 0 to one copy
                      .t          Z         transpose, padding with 0
                    xM                      pairwise xor
                  x1                        find all occurrences of 1
                 c                 2        chop into groups of 2
           f                                filter for groups T such that:
             aFT                              the absolute difference between its elements
            g   d                             is greater than or equal to d
   m                                        map for groups k:
     hk                                       first element
    ,  +ekd                                   pair with the last element plus d
 s                                        concatenate
}                                         deduplicate

Zestaw testowy

— Anders Kaseorg
źródło

Dostaję „[[3, 5], [6, 8], [0, 4], [1, 8]]” z „atattatt”. Czy [3,5] oznacza „tt”? Byłoby wspaniale, gdybyś mógł wyjaśnić algorytm, którego używałeś na wysokim poziomie.

@Lembik Tak, [i, j]reprezentuje początkowy kawałek między (0 indeksowane) znaków i-1i ii kończących się między znakami j-1i j. Jest to standardowa konwencja w Pyth i najbardziej rozsądnych językach, tak jak powinna (patrz tutaj i tutaj ).

— Anders Kaseorg

Świetny. Czy można intuicyjnie opisać swoje rozwiązanie? Niestety nie mogę odtworzyć kodu z twojego opisu kodu.

@Lembik Załóżmy, że szukamy serii d. Znajdujemy wszystkie lokalizacje, w których znak i pasuje do znaku i + d. Następnie znajdujemy serie co najmniej d kolejnych takich lokalizacji. Powtórz dla wszystkich d. Na koniec musimy deduplikować, ponieważ prawdziwy okres mógł być tylko dzielnikiem d.

— Anders Kaseorg

CJam, 66

q:A,2m*{~A>_@)_@<2*@@2*<=},{_2$-2>2,.+={+}&}*]{[_1=\)\0=2*)+]}%_&p

Wypróbuj online

Krótkie wyjaśnienie:

Algorytm działa w 4 krokach (pierwsze 3 z nich odpowiadają 3 głównym blokom, które można zaobserwować):

Znajdź wszystkie pary [indeks długości], które odpowiadają zduplikowanemu podciągowi (np. Aba aba aaacaacac); są to części serii.
Połączone pary, które są częścią tego samego przebiegu, tj. Kolejne indeksy i tę samą długość / okres.
Skonstruuj rzeczywiste przebiegi, biorąc minimalny indeks i maksymalny indeks + 2 * długość - 1.
Na koniec usuń zduplikowane przebiegi (które są tym samym interwałem uzyskanym w innym okresie)

Chciałbym zagrać w golfa bardziej, więc to wszystko może ulec zmianie.

— aditsu zrezygnowało, ponieważ SE jest ZŁEM
źródło

Dziękuję Ci za to. Czy mógłbyś wyjaśnić algorytm, którego również użyłeś?

@Lembik ok, zaktualizowano

— aditsu zostało zakończone, ponieważ SE jest ZŁY