[Pertanyaan ini adalah tindak lanjut untuk Menghitung berjalannya string ]

Periode pstring wadalah bilangan bulat positif psehingga w[i]=w[i+p] setiap kali kedua sisi persamaan ini didefinisikan. Biarkan per(w)menunjukkan ukuran periode terkecil w. Kami mengatakan bahwa string wadalah iff periodik per(w) <= |w|/2.

Jadi secara informal string periodik hanyalah string yang dibuat dari string lain yang diulang setidaknya satu kali. Satu-satunya komplikasi adalah bahwa pada akhir string kita tidak memerlukan salinan penuh dari string yang diulang selama itu diulang secara keseluruhan setidaknya sekali.

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 tersebut ababaadalah periodik sebagai per(ababa) = 2.

Sebagai lebih banyak contoh abcabca,, ababababadan abcabcabcjuga berkala.

Bagi mereka yang suka regex, yang ini mendeteksi apakah suatu string periodik atau tidak:

\b(\w*)(\w+\1)\2+\b

Tugasnya adalah untuk menemukan semua substring periodik maksimal dalam string yang lebih panjang. Ini kadang-kadang disebut run dalam literatur.

Substring wadalah substring periodik maksimal (run) jika periodik dan tidak w[i-1] = w[i-1+p]juga w[j+1] = w[j+1-p]. Secara informal, "jalankan" tidak dapat dimuat dalam "lari" yang lebih besar dengan periode yang sama.

Karena dua run dapat mewakili string karakter yang sama yang terjadi di tempat yang berbeda di string keseluruhan, kami akan mewakili run dengan interval. Berikut adalah definisi di atas yang diulang dalam hal interval.

Suatu run (atau substring periodik maksimal) dalam suatu string Tadalah suatu interval [i...j]dengan j>=i, sedemikian rupa sehingga

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

Ditunjukkan oleh RUNS(T)set run dalam string T.

Contoh menjalankan

• Keempat substring periodik maksimal (berjalan) dalam string T = atattattadalah T[4,5] = tt, T[7,8] = tt, T[1,4] = atat, T[2,8] = tattatt.

• String T = aabaabaaaacaacacberisi berikut 7 substring periodik maksimal (berjalan): T[1,2] = aa, T[4,5] = aa, T[7,10] = aaaa, T[12,13] = aa, T[13,16] = acac, T[1,8] = aabaabaa, T[9,15] = aacaaca.

• String T = atatbatatbberisi tiga run berikut. Mereka adalah: T[1, 4] = atat, T[6, 9] = atatdan T[1, 10] = atatbatatb.

Di sini saya menggunakan pengindeksan 1.

Tugas

Tulis kode sehingga untuk setiap bilangan bulat n mulai dari 2, Anda menghasilkan jumlah run terbanyak yang terkandung dalam string biner panjang mana pun n.

Skor

Skor Anda adalah yang tertinggi yang nAnda capai dalam 120 detik sehingga untuk semua k <= n, tidak ada orang lain yang memposting jawaban yang benar lebih tinggi dari Anda. Jelas jika Anda memiliki semua jawaban optimal maka Anda akan mendapatkan skor untuk tertinggi yang nAnda posting. Namun, meskipun jawaban Anda tidak optimal, Anda masih bisa mendapatkan skor jika tidak ada orang lain yang bisa mengalahkannya.

Bahasa dan perpustakaan

Anda dapat menggunakan bahasa dan perpustakaan yang tersedia yang Anda suka. Jika memungkinkan, alangkah baiknya untuk dapat menjalankan kode Anda, jadi harap sertakan penjelasan lengkap tentang cara menjalankan / kompilasi kode Anda di Linux jika memungkinkan.

Contoh optima

Berikut ini: n, optimum number of runs, example string.

2 1 00
3 1 000
4 2 0011
5 2 00011
6 3 001001
7 4 0010011
8 5 00110011
9 5 000110011
10 6 0010011001
11 7 00100110011
12 8 001001100100
13 8 0001001100100
14 10 00100110010011
15 10 000100110010011
16 11 0010011001001100
17 12 00100101101001011
18 13 001001100100110011
19 14 0010011001001100100
20 15 00101001011010010100
21 15 000101001011010010100
22 16 0010010100101101001011

Apa sebenarnya yang harus saya hasilkan kode?

Untuk setiap nkode Anda harus menampilkan string tunggal dan jumlah berjalan di dalamnya.

Mesin Saya Pengaturan waktu akan dijalankan pada mesin saya. Ini adalah instalasi ubuntu standar pada Prosesor Delapan Core AMD FX-8350. Ini juga berarti saya harus dapat menjalankan kode Anda.

Memimpin jawaban

• 49 oleh Anders Kaseorg di C . Single berulir dan jalankan dengan L = 12 (2GB RAM).
• 27 oleh cdlane di C .

C

Ini melakukan pencarian rekursif untuk solusi optimal, dipangkas berat menggunakan batas atas pada jumlah run yang dapat diselesaikan oleh sisa string yang tidak diketahui. Perhitungan batas atas menggunakan tabel pencarian raksasa yang ukurannya dikontrol oleh konstanta L( L=11: 0,5 GiB,: L=122 GiB,: L=138 GiB).

Di laptop saya, ini naik melalui n = 50 dalam 100 detik; baris berikutnya muncul di 142 detik.

#include <stdbool.h>
#include <stdint.h>
#include <stdio.h>
#include <string.h>

#define N (8*sizeof(unsigned long long))
#define L 13
static bool a[N], best_a[N];
static int start[N/2 + 1], best_runs;
static uint8_t end_runs[2 << 2*L][2], small[N + 1][2 << 2*L];

static inline unsigned next_state(unsigned state, int b)
{
    state *= 2;
    state += b;
    if (state >= 2 << 2*L) {
        state &= ~(2 << 2*L);
        state |= 1 << 2*L;
    }
    return state;
}

static void search(int n, int i, int runs, unsigned state)
{
    if (i == n) {
        int r = runs;
        unsigned long long m = 0;
        for (int p = n / 2; p > 0; p--) {
            if (i - start[p] >= 2*p && !(m & 1ULL << start[p])) {
                m |= 1ULL << start[p];
                r++;
            }
        }
        if (r > best_runs) {
            best_runs = r;
            memcpy(best_a, a, n*sizeof(a[0]));
        }
    } else {
        a[i] = false;
        do {
            int r = runs, bound = 0, saved = 0, save_p[N/2], save_start[N/2], p, s = next_state(state, a[i]);
            unsigned long long m = 0;
            for (p = n/2; p > i; p--)
                if (p > L)
                    bound += (n - p + 1)/(p + 1);
            for (; p > 0; p--) {
                if (a[i] != a[i - p]) {
                    if (i - start[p] >= 2*p && !(m & 1ULL << start[p])) {
                        m |= 1ULL << start[p];
                        r++;
                    }
                    save_p[saved] = p;
                    save_start[saved] = start[p];
                    saved++;
                    start[p] = i + 1 - p;
                    if (p > L)
                        bound += (n - i)/(p + 1);
                } else {
                    if (p > L)
                        bound += (n - (start[p] + p - 1 > i - p ? start[p] + p - 1 : i - p))/(p + 1);
                }
            }
            bound += small[n - i - 1][s];

            if (r + bound > best_runs)
                search(n, i + 1, r, s);
            while (saved--)
                start[save_p[saved]] = save_start[saved];
        } while ((a[i] = !a[i]));
    }
}

int main()
{
    for (int n = 0; n <= N; n++) {
        if (n <= 2*L) {
            for (unsigned state = 1U << n; state < 2U << n; state++) {
                for (int b = 0; b < 2; b++) {
                    int r = 0;
                    unsigned long long m = 0;
                    for (int p = n / 2; p > 0; p--) {
                        if ((b ^ state >> (p - 1)) & 1) {
                            unsigned k = state ^ state >> p;
                            k &= -k;
                            k <<= p;
                            if (!(k & ~(~0U << n)))
                                k = 1U << n;
                            if (!((m | ~(~0U << 2*p)) & k)) {
                                m |= k;
                                r++;
                            }
                        }
                    }
                    end_runs[state][b] = r;
                }
                small[0][state] = end_runs[state][0] + end_runs[state][1];
            }
        }

        for (int l = 2*L < n - 1 ? 2*L : n - 1; l >= 0; l--) {
            for (unsigned state = 1U << l; state < 2U << l; state++) {
                int r0 = small[n - l - 1][next_state(state, 0)] + end_runs[state][0],
                    r1 = small[n - l - 1][next_state(state, 1)] + end_runs[state][1];
                small[n - l][state] = r0 > r1 ? r0 : r1;
            }
        }

        if (n >= 2) {
            search(n, 1, 0, 2U);
            printf("%d %d ", n, best_runs);
            for (int i = 0; i < n; i++)
                printf("%d", best_a[i]);
            printf("\n");
            fflush(stdout);
            best_runs--;
        }
    }
    return 0;
}

Keluaran:

$ gcc -mcmodel=medium -O2 runs.c -o runs
$ ./runs
2 1 00
3 1 000
4 2 0011
5 2 00011
6 3 001001
7 4 0010011
8 5 00110011
9 5 000110011
10 6 0010011001
11 7 00100110011
12 8 001001100100
13 8 0001001100100
14 10 00100110010011
15 10 000100110010011
16 11 0010011001001100
17 12 00100101101001011
18 13 001001100100110011
19 14 0010011001001100100
20 15 00101001011010010100
21 15 000101001011010010100
22 16 0010010100101101001011
23 17 00100101001011010010100
24 18 001001100100110110011011
25 19 0010011001000100110010011
26 20 00101001011010010100101101
27 21 001001010010110100101001011
28 22 0010100101101001010010110100
29 23 00101001011010010100101101011
30 24 001011010010110101101001011010
31 25 0010100101101001010010110100101
32 26 00101001011010010100101101001011
33 27 001010010110100101001011010010100
34 27 0001010010110100101001011010010100
35 28 00100101001011010010100101101001011
36 29 001001010010110100101001011010010100
37 30 0010011001001100100010011001001100100
38 30 00010011001001100100010011001001100100
39 31 001001010010110100101001011010010100100
40 32 0010010100101101001010010110100101001011
41 33 00100110010001001100100110010001001100100
42 35 001010010110100101001011010110100101101011
43 35 0001010010110100101001011010110100101101011
44 36 00101001011001010010110100101001011010010100
45 37 001001010010110100101001011010110100101101011
46 38 0010100101101001010010110100101001011010010100
47 39 00101101001010010110100101101001010010110100101
48 40 001010010110100101001011010010110101101001011010
49 41 0010100101101001010010110100101101001010010110100
50 42 00101001011010010100101101001011010110100101101011
51 43 001010010110100101001011010110100101001011010010100

Berikut adalah semua urutan optimal untuk n ≤ 64 (bukan hanya leksikografis pertama), yang dihasilkan oleh versi modifikasi dari program ini dan banyak jam perhitungan.

Urutan hampir optimal yang luar biasa

Awalan dari urutan fraktal tak terbatas

1010010110100101001011010010110100101001011010010100101…

yang tidak berubah di bawah transformasi 101 ↦ 10100, 00 ↦ 101:

  101   00  101   101   00  101   00  101   101   00  101   101   00  …
= 10100 101 10100 10100 101 10100 101 10100 10100 101 10100 10100 101 …

tampaknya memiliki jumlah run yang sangat optimal — selalu dalam 2 dari optimal untuk n ≤ 64. Jumlah run dalam karakter n pertama dibagi dengan pendekatan n (13 - 5√5) / 2 ≈ 0,90983. Tetapi ternyata ini bukan rasio yang optimal — lihat komentar.

Karena ini bukan perlombaan jika hanya ada satu kuda, saya mengirimkan solusi saya meskipun itu hanya sebagian kecil dari kecepatan Anders Kaseorg dan hanya sepertiga sebagai samar. Kompilasi dengan:

gcc -O2 run-count.c -o run-count

Inti dari algoritma saya adalah perubahan sederhana dan skema XOR:

Jalankan angka nol dalam hasil XOR yang lebih besar dari atau sama dengan periode / shift saat ini menunjukkan menjalankan dalam string asli untuk periode ini. Dari sini Anda bisa mengetahui berapa lama proses itu dan di mana ia mulai dan berakhir. Sisa kode adalah overhead, mengatur situasi dan mendekode hasilnya.

Saya berharap ini akan menghasilkan setidaknya 28 setelah dua menit pada mesin Lembik. (Saya menulis versi pthread, tetapi hanya berhasil membuatnya berjalan lebih lambat.)

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <stdbool.h>

enum { START = 0, WIDTH } ;

// Compare and shuffle just one thing while storing two
typedef union {
    uint16_t token;
    uint8_t data[sizeof(uint16_t)];
} overlay_t;

#define SENTINAL (0)  // marks the end of an array of overlay_t

#define NUMBER_OF_BITS (8 * sizeof(uint64_t))

void period_runs(uint64_t xor_bits, uint8_t nbits, uint8_t period, overlay_t *results) {

    overlay_t *results_ptr = results;
    uint8_t count = 0;

    for (uint8_t position = 0; position < nbits; position++) {

        if (xor_bits & 1ULL) {

            if ((nbits - position) < period) {
                break;  // no room left to succeed further
            }

            if (count >= period) {  // we found a run

                results_ptr->data[START] = position - (count - 1);
                results_ptr->data[WIDTH] = period + count;
                results_ptr++;
            }

            count = 0;
        } else {

            count++;
        }

        xor_bits >>= 1;
    }

    if (count >= period) {  // process the final run, if any

        results_ptr->data[START] = 0;
        results_ptr->data[WIDTH] = period + count;
        results_ptr++;
    }

    results_ptr->token = SENTINAL;
}

void number_runs(uint64_t number, uint8_t bit_length, overlay_t *results) {

    overlay_t sub_results[bit_length];
    uint8_t limit = bit_length / 2 + 1;
    uint64_t mask = (1ULL << (bit_length - 1)) - 1;

    overlay_t *results_ptr = results;
    results_ptr->token = SENTINAL;

    for (uint8_t period = 1; period < limit; period++) {

        uint64_t xor_bits = mask & (number ^ (number >> period));  // heart of the code
        period_runs(xor_bits, bit_length - period, period, sub_results);

        for (size_t i = 0; sub_results[i].token != SENTINAL; i++) {

            bool stop = false;  // combine previous and current results

            for (size_t j = 0; !stop && results[j].token != SENTINAL; j++) {

                // lower period result disqualifies higher period result over the same span 
                stop = (sub_results[i].token == results[j].token);
            }

            if (!stop) {

                (results_ptr++)->token = sub_results[i].token;
                results_ptr->token = SENTINAL;
            }
        }

        mask >>= 1;
    }
}

int main() {

    overlay_t results[NUMBER_OF_BITS];

    for (uint8_t bit_length = 2; bit_length < 25; bit_length++) {

        int best_results = -1;
        uint64_t best_number = 0;

        for (uint64_t number = 1ULL << (bit_length - 1); number < (1ULL << bit_length); number++) {

            // from the discussion comments, I should be able to solve this
            // with just bit strings that begin "11...", so toss the rest
            if ((number & (1ULL << (bit_length - 2))) == 0ULL) {

                continue;
            }

            uint64_t reversed = 0;

            for (uint8_t i = 0; i < bit_length; i++) {

                if (number & (1ULL << i)) {

                    reversed |= (1ULL << ((bit_length - 1) - i));
                }
            }

            if (reversed > number) {

                continue;  // ~ 1/4 of bit_strings are simply reversals, toss 'em
            }

            number_runs(number, bit_length, results);
            overlay_t *results_ptr = results;
            int count = 0;

            while ((results_ptr++)->token != SENTINAL) {

                count++;
            }

            if (count > best_results) {

                best_results = count;
                best_number = number;
            }
        }

        char *best_string = malloc(bit_length + 1);
        uint64_t number = best_number;
        char *string_ptr = best_string;

        for (int i = bit_length - 1; i >= 0; i--) {

            *(string_ptr++) = (number & (1ULL << i)) ? '1' : '0';
        }

        *string_ptr = '\0';

        printf("%u %d %s\n", bit_length, best_results, best_string);

        free(best_string);
    }

    return 0;
}

Keluaran:

> gcc -O2 run-count.c -o run-count
> ./run-count
2 1 11
3 1 110
4 2 1100
5 2 11000
6 3 110011
7 4 1100100
8 5 11001100
9 5 110010011
10 6 1100110011
11 7 11001100100
12 8 110110011011
13 8 1100100010011
14 10 11001001100100
15 10 110010011001000
16 11 1100100110010011
17 12 11001100100110011
18 13 110011001001100100
19 14 1101001011010010100
20 15 11010110100101101011
21 15 110010011001001100100
22 16 1100101001011010010100
23 17 11010010110100101001011
24 18 110100101001011010010100
25 19 1100100110010001001100100
26 20 11010010100101101001010010
27 21 110010011001000100110010011
28 22 1101001010010110100101001011