Pertimbangkan definisi berikut yang diambil dari Jumlah run dalam string oleh W. Rytter. Perhatikan bahwa kata, string, dan substring semuanya sinonim secara kasar.

Jalankan dalam sebuah string adalah segmen periodik yang tidak dapat diperbandingkan (dengan periode minimal yang sama) dalam sebuah string.

Suatu periode p dari suatu kata w adalah setiap bilangan bulat positif p sehingga w [i] = w [i + p] setiap kali kedua sisi dari persamaan ini didefinisikan. Biarkan per (w) menunjukkan ukuran periode terkecil w. Kami mengatakan bahwa kata w adalah iff periodik per (w) <= | w | / 2.

Misalnya, perhatikan string x = abcab. per(abcab) = 3sebagai x[1] = x[1+3] = a, x[2]=x[2+3] = bdan tidak ada periode yang lebih kecil. abcabKarenanya string tidak periodik. Namun, string ababbersifat periodik sesuai (abab) = 2.

Suatu run (atau periodisitas maksimal) dalam string w adalah interval [i ... j] dengan j> = i, sedemikian rupa sehingga

• w [i ... j] adalah kata periodik dengan periode p = per (w [i ... j])
• Itu maksimal. Secara formal, tidak w [i-1] = w [i-1 + p] atau w [j + 1] = w [j + 1-p]. Secara informal, proses tidak dapat dimuat dalam proses yang lebih besar dengan periode yang sama.

Ditunjukkan oleh RUNS (w) himpunan run w.

Contohnya

Empat run atattattadalah [4,5] = tt, [7,8] = tt, [1,4] = atat, [2,8] = tattatt.

String aabaabaaaacaacacberisi 7 run berikut:

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

Output Anda harus berupa daftar run. Setiap proses harus menentukan interval yang diwakilinya tetapi tidak perlu menampilkan substring itu sendiri. Pemformatan yang tepat bisa apa saja yang nyaman bagi Anda.

Contoh-contoh menggunakan pengindeksan 1 tetapi Anda bebas menggunakan pengindeksan 0 jika lebih nyaman.

TUGAS

Tulis kode yang diberi string w, output RUNS (w).

Bahasa dan input

Anda dapat menggunakan bahasa apa pun yang Anda suka dan mengambil string input dalam bentuk apa pun yang paling nyaman. Anda harus memberikan program lengkap dan Anda harus menunjukkan contoh kode Anda berjalan pada input contoh.

Pyth, 38 byte

{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

Suite uji

CJam, 66

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

Cobalah online

Penjelasan singkat:

Algoritma ini bekerja dalam 4 langkah (3 langkah pertama yang sesuai dengan 3 blok utama yang dapat Anda amati):

1. Temukan semua pasangan [indeks panjang] yang sesuai dengan substring yang digandakan (seperti aba aba aaacaacac); ini adalah bagian dari proses.
2. Pasangan gabungan yang merupakan bagian dari proses yang sama, yaitu indeks berurutan dan panjang / periode yang sama.
3. Bangun lari aktual, dengan mengambil indeks minimum dan indeks maksimum + 2 * panjang - 1.
4. Pada akhirnya, hapus duplikasi berjalan (yang merupakan interval yang sama diperoleh dengan periode yang berbeda)

Saya ingin bermain golf lebih banyak, jadi ini semua bisa berubah.