Tugas Anda adalah untuk memecahkan masalah Sub- urutan Umum Terpanjang untuk n string dengan panjang 1000.

Sebuah solusi yang valid untuk masalah LCS untuk dua atau lebih string S ₁ , ... S _n adalah string T panjang maksimal sehingga karakter dari T muncul di semua S _i , dalam urutan yang sama seperti pada T .

Perhatikan bahwa T tidak harus menjadi sub string dari S _i .

Kami telah memecahkan masalah ini dalam jumlah kode terpendek . Kali ini, ukuran tidak masalah.

Contoh

Senar axbyczdan xaybzcmemiliki 8 urutan umum panjang 3:

abc abz ayc ayz xbc xbz xyc xyz

Semua ini akan menjadi solusi yang valid untuk masalah LCS.

Detail

Tulis program lengkap yang menyelesaikan masalah LCS, seperti dijelaskan di atas, dengan mematuhi aturan berikut:

• Input akan terdiri dari dua atau lebih string 1000, yang terdiri dari karakter ASCII dengan titik kode antara 0x30 dan 0x3F.

• Anda harus membaca input dari STDIN.

  Anda memiliki dua pilihan untuk format input:

  • Setiap string (termasuk yang terakhir) diikuti oleh linefeed.

  • String dirantai bersama-sama tanpa pemisah dan tanpa linefeed line.

• Jumlah string akan diteruskan sebagai parameter baris perintah ke program Anda.

• Anda harus menulis output, yaitu, salah satu solusi yang valid untuk LCS, untuk STDOUT, diikuti oleh satu linefeed.

• Bahasa pilihan Anda harus memiliki kompiler / juru bahasa gratis (seperti dalam bir) untuk sistem operasi saya (Fedora 21).

• Jika Anda memerlukan flag kompiler atau juru bahasa tertentu, harap sebutkan di posting Anda.

Mencetak gol

Saya akan menjalankan kode Anda dengan string 2, 3, dll. Hingga diperlukan waktu lebih dari 120 detik untuk mencetak solusi yang valid. Ini berarti Anda memiliki 120 detik untuk setiap nilai n .

Jumlah string tertinggi yang menyelesaikan kode dalam waktu adalah skor Anda.

Dalam hal skor n terikat , pengajuan yang memecahkan masalah untuk n string dalam waktu singkat akan dinyatakan sebagai pemenang.

Semua pengiriman akan dihitung waktunya mesin saya (Intel Core i7-3770, 16 GiB RAM, tanpa swap).

The n string dari (n-1) ^th tes akan dihasilkan dengan menelepon rand n(dan pengupasan linefeeds, jika diminta), di mana randdidefinisikan sebagai berikut:

rand()
{
    head -c$[500*$1] /dev/zero |
    openssl enc -aes-128-ctr -K 0 -iv $1 |
    xxd -c500 -ps |
    tr 'a-f' ':-?'
}

Kuncinya ada 0pada kode di atas, tetapi saya berhak untuk mengubahnya ke nilai yang tidak diungkapkan jika saya mencurigai ada orang yang (sebagian) meng-hardcoding output.

C, n = 3 dalam ~ 7 detik

Algoritma

Algoritme adalah generalisasi langsung dari solusi pemrograman dinamis standar ke nurutan. Untuk 2 string Adan B, perulangan standar terlihat seperti ini:

L(p, q) = 1 + L(p - 1, q - 1)           if A[p] == B[q]
        = max(L(p - 1, q), L(p, q - 1)) otherwise

Untuk 3 senar A, B, Csaya gunakan:

L(p, q, r) = 1 + L(p - 1, q - 1, r - 1)                          if A[p] == B[q] == C[r]
           = max(L(p - 1, q, r), L(p, q - 1, r), L(p, q, r - 1)) otherwise

Kode mengimplementasikan logika ini untuk nilai arbitrer dari n.

Efisiensi

Kompleksitas kode saya adalah O (s ^ n), dengan spanjang string. Berdasarkan apa yang saya temukan, sepertinya masalahnya adalah NP-complete. Jadi, sementara algoritma yang diposting sangat tidak efisien untuk nilai yang lebih besar n, mungkin sebenarnya tidak mungkin dilakukan secara besar-besaran dengan lebih baik. Satu-satunya hal yang saya lihat adalah beberapa pendekatan yang meningkatkan efisiensi untuk huruf kecil. Karena alfabetnya cukup kecil di sini (16), itu bisa mengarah pada peningkatan. Saya masih memprediksi bahwa tidak ada yang akan menemukan solusi yang sah yang lebih tinggi daripada n = 4dalam 2 menit, dan n = 4sudah terlihat ambisius.

Saya mengurangi penggunaan memori dalam implementasi awal, sehingga bisa menangani n = 4 waktu yang cukup. Tapi itu hanya menghasilkan panjang urutan, bukan urutan itu sendiri. Periksa riwayat revisi posting ini untuk melihat kode itu.

Kode

Karena loop lebih dari matriks n-dimensi membutuhkan lebih banyak logika daripada loop tetap, saya menggunakan loop tetap untuk dimensi terendah, dan hanya menggunakan logika looping umum untuk dimensi yang tersisa.

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

#define N_MAX 4

int main(int argc, char* argv[]) {
    int nSeq = argc - 1;
    if (nSeq > N_MAX) {
        nSeq = N_MAX;
    }

    char** seqA = argv + 1;

    uint64_t totLen = 1;
    uint64_t lenA[N_MAX] = {0};
    uint64_t offsA[N_MAX] = {1};
    uint64_t offsSum = 0;
    uint64_t posA[N_MAX] = {0};

    for (int iSeq = 0; iSeq < nSeq; ++iSeq) {
        lenA[iSeq] = strlen(seqA[iSeq]);
        totLen *= lenA[iSeq] + 1;

        if (iSeq + 1 < nSeq) {
            offsA[iSeq + 1] = totLen;
        }

        offsSum += offsA[iSeq];
    }

    uint16_t* mat = calloc(totLen, 2);
    uint64_t idx = offsSum;

    for (;;) {
        for (uint64_t pos0 = 0; pos0 < lenA[0]; ++pos0) {
            char firstCh = seqA[0][pos0];
            int isSame = 1;
            uint16_t maxVal = mat[idx - 1];

            for (int iSeq = 1; iSeq < nSeq; ++iSeq) {
                char ch = seqA[iSeq][posA[iSeq]];
                isSame &= (ch == firstCh);

                uint16_t val = mat[idx - offsA[iSeq]];
                if (val > maxVal) {
                    maxVal = val;
                }
            }

            if (isSame) {
                mat[idx] = mat[idx - offsSum] + 1;
            } else {
                mat[idx] = maxVal;
            }

            ++idx;
        }

        idx -= lenA[0];

        int iSeq = 1;
        while (iSeq < nSeq && posA[iSeq] == lenA[iSeq] - 1) {
            posA[iSeq] = 0;
            idx -= (lenA[iSeq] - 1) * offsA[iSeq];
            ++iSeq;
        }
        if (iSeq == nSeq) {
            break;
        }

        ++posA[iSeq];
        idx += offsA[iSeq];
    }

    int score = mat[totLen - 1];

    char* resStr = malloc(score + 1);
    resStr[score] = '\0';

    for (int iSeq = 0; iSeq < nSeq; ++iSeq) {
        posA[iSeq] = lenA[iSeq] - 1;
    }

    idx = totLen - 1;
    int resIdx = score - 1;

    while (resIdx >= 0) {
        char firstCh = seqA[0][posA[0]];
        int isSame = 1;
        uint16_t maxVal = mat[idx - 1];
        int maxIdx = 0;

        for (int iSeq = 1; iSeq < nSeq; ++iSeq) {
            char ch = seqA[iSeq][posA[iSeq]];
            isSame &= (ch == firstCh);

            uint16_t val = mat[idx - offsA[iSeq]];
            if (val > maxVal) {
                maxVal = val;
                maxIdx = iSeq;
            }
        }

        if (isSame) {
            resStr[resIdx--] = firstCh;
            for (int iSeq = 0; iSeq < nSeq; ++iSeq) {
                --posA[iSeq];
            }
            idx -= offsSum;
        } else {
            --posA[maxIdx];
            idx -= offsA[maxIdx];
        }
    }

    free(mat);

    printf("score: %d\n", score);
    printf("%s\n", resStr);

    return 0;
}

Instruksi untuk Berlari

Untuk berlari:

• Simpan kode dalam file, mis lcs.c .

• Kompilasi dengan opsi optimasi tinggi. Saya menggunakan:

  clang -O3 lcs.c
  

  Di Linux, saya akan mencoba:

  gcc -Ofast lcs.c
  

• Jalankan dengan 2 hingga 4 urutan yang diberikan sebagai argumen baris perintah:

  ./a.out axbycz xaybzc
  

  Kutip tunggal argumen baris perintah jika perlu, karena alfabet yang digunakan untuk contoh berisi karakter khusus shell.

Hasil

test2.shdan test3.shmerupakan urutan uji dari Dennis. Saya tidak tahu hasil yang benar, tetapi hasilnya terlihat setidaknya masuk akal.

$ ./a.out axbycz xaybzc
score: 3
abc

$ time ./test2.sh 
score: 391
16638018802020>3??3232270178;47240;24331395?<=;99=?;178675;866002==23?87?>978891>=9<6<9381992>>7030829?255>6804:=3>:;60<9384=081;0:?66=51?0;5090724<85?>>:2>7>3175?::<9199;5=0:494<5<:7100?=95<91>1887>33>67710==;48<<327::>?78>77<6:2:02:<7=5?:;>97<993;57=<<=:2=9:8=118563808=962473<::8<816<464<1==925<:5:22?>3;65=>=;27?7:5>==3=4>>5>:107:20575347>=48;<7971<<245<??219=3991=<96<??735698;62?<98928

real  0m0.012s
user  0m0.008s
sys   0m0.003s

$ time ./test3.sh 
score: 269
662:2=2::=6;738395=7:=179=96662649<<;?82?=668;2?603<74:6;2=04=>6;=6>=121>1>;3=22=3=3;=3344>0;5=7>>7:75238;559133;;392<69=<778>3?593?=>9799<1>79827??6145?7<>?389?8<;;133=505>2703>02?323>;693995:=0;;;064>62<0=<97536342603>;?92034<?7:=;2?054310176?=98;5437=;13898748==<<?4

real  0m7.218s
user  0m6.701s
sys   0m0.513s

Jawaban ini saat ini rusak karena bug. Memperbaiki segera ...

C, 2 string dalam ~ 35 detik

Ini sangat banyak pekerjaan yang sedang berlangsung (seperti yang ditunjukkan oleh kekacauan yang mengerikan), tetapi mudah-mudahan itu memicu beberapa jawaban yang bagus!

Kode:

#include "stdlib.h"
#include "string.h"
#include "stdio.h"
#include "time.h"

/* For the versatility */
#define MIN_CODEPOINT 0x30
#define MAX_CODEPOINT 0x3F
#define NUM_CODEPOINT (MAX_CODEPOINT - MIN_CODEPOINT + 1)
#define CTOI(c) (c - MIN_CODEPOINT)

#define SIZE_ARRAY(x) (sizeof(x) / sizeof(*x))

int LCS(char** str, int num);
int getshared(char** str, int num);
int strcount(char* str, char c);

int main(int argc, char** argv) {
    char** str = NULL;
    int num = 0;
    int need_free = 0;
    if (argc > 1) {
        str = &argv[1];
        num = argc - 1;
    }
    else {
        scanf(" %d", &num);
        str = malloc(sizeof(char*) * num);
        if (!str) {
            printf("Allocation error!\n");
            return 1;
        }

        int i;
        for (i = 0; i < num; i++) {
            /* No string will exceed 1000 characters */
            str[i] = malloc(1001);
            if (!str[i]) {
                printf("Allocation error!\n");
                return 1;
            }

            scanf(" %1000s", str[i]);

            str[i][1000] = '\0';
        }

        need_free = 1;
    }

    clock_t start = clock();

    /* The call to LCS */
    int size = LCS(str, num);

    double dt = ((double)(clock() - start)) / CLOCKS_PER_SEC;
    printf("Size: %d\n", size);
    printf("Elapsed time on LCS call: %lf s\n", dt);

    if (need_free) {
        int i;
        for (i = 0; i < num; i++) {
            free(str[i]);
        }
        free(str);
    }

    return 0;
}

/* Some terribly ugly global variables... */
int depth, maximum, mapsize, lenmap[999999][2];
char* (strmap[999999][20]);
char outputstr[1000];

/* Solves the LCS problem on num strings str of lengths len */
int LCS(char** str, int num) {
    /* Counting variables */
    int i, j;

    if (depth + getshared(str, num) <= maximum) {
        return 0;
    }

    char* replace[num];
    char match;
    char best_match = 0;
    int earliest_set = 0;
    int earliest[num];
    int all_late;
    int all_early;
    int future;
    int best_future = 0;
    int need_future = 1;

    for (j = 0; j < mapsize; j++) {
        for (i = 0; i < num; i++)
            if (str[i] != strmap[j][i])
                break;
        if (i == num) {
            best_match = lenmap[j][0];
            best_future = lenmap[j][1];
            need_future = 0;
            if (best_future + depth < maximum || !best_match)
                goto J;
            else {
                match = best_match;
                goto K;
            }
        }
    }

    for (match = MIN_CODEPOINT; need_future && match <= MAX_CODEPOINT; match++) {

    K:
        future = 1;
        all_late = earliest_set;
        all_early = 1;
        for (i = 0; i < num; replace[i++]++) {
            replace[i] = strchr(str[i], match);
            if (!replace[i]) {
                future = 0;
                break;
            }

            if (all_early && earliest_set && replace[i] - str[i] > earliest[i])
                all_early = 0;
            if (all_late && replace[i] - str[i] < earliest[i])
                all_late = 0;
        }
        if (all_late) {
            future = 0;
        }

    I:
        if (future) {
            if (all_early || !earliest_set) {
                for (i = 0; i < num; i++) {
                    earliest[i] = (int)(replace[i] - str[i]);
                }
            }

            /* The recursive bit */
            depth++;
            future += LCS(replace, num);
            depth--;

            best_future = future > best_future ? (best_match = match), future : best_future;
        }
    }

    if (need_future) {
        for (i = 0; i < num; i++)
            strmap[mapsize][i] = str[i];
        lenmap[mapsize][0] = best_match;
        lenmap[mapsize++][1] = best_future;
    }

J:
    if (depth + best_future >= maximum) {
        maximum = depth + best_future;
        outputstr[depth] = best_match;
    }

    if (!depth) {
        mapsize = 0;
        maximum = 0;
        puts(outputstr);
    }

    return best_future;
}

/* Return the number of characters total (not necessarily in order) that the strings all share */
int getshared(char** str, int num) {
    int c, i, tot = 0, min;
    for (c = MIN_CODEPOINT; c <= MAX_CODEPOINT; c++) {
        min = strcount(str[0], c);
        for (i = 1; i < num; i++) {
            int count = strcount(str[i], c);
            if (count < min) {
                min = count;
            }
        }
        tot += min;
    }

    return tot;
}

/* Count the number of occurrences of c in str */
int strcount(char* str, char c) {
    int tot = 0;
    while ((str = strchr(str, c))) {
        str++, tot++;
    }
    return tot;
}

Fungsi yang relevan yang melakukan semua perhitungan LCS adalah fungsi LCS. Kode di atas akan mengatur waktu panggilannya sendiri ke fungsi ini.

Simpan sebagai main.cdan kompilasi dengan:gcc -Ofast main.c -o FLCS

Kode dapat dijalankan dengan argumen baris perintah atau melalui stdin. Saat menggunakan stdin, ia mengharapkan sejumlah string diikuti oleh string itu sendiri.

~ Me$ ./FLCS "12345" "23456"
2345
Size: 4
Elapsed time on LCS call: 0.000056 s

Atau:

~ Me$ ./FLCS
6 
2341582491248123139182371298371239813
2348273123412983476192387461293472793
1234123948719873491234120348723412349
1234129388234888234812834881423412373
1111111112341234128469128377293477377
1234691237419274737912387476371777273
1241231212323
Size: 13
Elapsed time on LCS call: 0.001594 s

Pada kotak Mac OS X dengan 1.7Ghz Intel Core i7 dan test case yang disediakan Dennis, kami mendapatkan output berikut untuk 2 string:

16638018800200>3??32322701784=4240;24331395?<;=99=?;178675;866002==23?87?>978891>=9<66=381992>>7030829?25265804:=3>:;60<9384=081;08?66=51?0;509072488>2>924>>>3175?::<9199;330:494<51:>748571?153994<45<??20>=3991=<962508?7<2382?489
Size: 386
Elapsed time on LCS call: 33.245087 s

Pendekatannya sangat mirip dengan pendekatan saya dengan tantangan sebelumnya, di sini . Selain pengoptimalan sebelumnya, kami sekarang memeriksa jumlah total karakter yang dibagi antara string di setiap rekursi dan keluar lebih awal jika tidak ada cara untuk mendapatkan substring yang lebih lama daripada yang sudah ada.

Untuk saat ini, ia menangani 2 string, tetapi cenderung mengalami crash-y pada lebih banyak. Lebih banyak peningkatan dan penjelasan yang lebih baik untuk datang!