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.

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

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ć):

1. Znajdź wszystkie pary [indeks długości], które odpowiadają zduplikowanemu podciągowi (np. Aba aba aaacaacac); są to części serii.
2. Połączone pary, które są częścią tego samego przebiegu, tj. Kolejne indeksy i tę samą długość / okres.
3. Skonstruuj rzeczywiste przebiegi, biorąc minimalny indeks i maksymalny indeks + 2 * długość - 1.
4. 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.