Ihre Aufgabe ist es, das Problem der längsten gemeinsamen Folge für n Zeichenfolgen mit einer Länge von 1000 zu lösen .

Eine gültige Lösung für das LCS-Problem für zwei oder mehr Zeichenfolgen S ₁ ,… S _n ist eine beliebige Zeichenfolge T mit maximaler Länge, so dass die Zeichen von T in allen S _i in derselben Reihenfolge wie in T erscheinen .

Beachten Sie, dass T nicht Teil sein muss Zeichenfolge von S _i .

Wir haben dieses Problem bereits in kürzester Zeit gelöst . Diesmal spielt die Größe keine Rolle.

Beispiel

Die Strings axbyczund xaybzchaben 8 gemeinsame Teilsequenzen der Länge 3:

abc abz ayc ayz xbc xbz xyc xyz

All dies wäre eine gültige Lösung für das LCS-Problem.

Einzelheiten

Schreiben Sie ein vollständiges Programm, das das LCS-Problem wie oben erläutert löst und dabei die folgenden Regeln einhält:

• Die Eingabe besteht aus zwei oder mehr Zeichenfolgen der Länge 1000, die aus ASCII-Zeichen mit Codepunkten zwischen 0x30 und 0x3F bestehen.

• Sie müssen die Eingabe von STDIN lesen.

  Sie haben zwei Möglichkeiten für das Eingabeformat:

  • Auf jede Zeichenfolge (einschließlich der letzten) folgt ein Zeilenvorschub.

  • Die Saiten sind ohne Trennzeichen und ohne nachlaufenden Zeilenvorschub miteinander verkettet.

• Die Anzahl der Zeichenfolgen wird als Befehlszeilenparameter an Ihr Programm übergeben.

• Sie müssen die Ausgabe, dh eine der gültigen Lösungen für das LCS, in STDOUT schreiben, gefolgt von einem Zeilenvorschub.

• Ihre bevorzugte Sprache muss einen kostenlosen Compiler / Interpreter (wie in Bier) für mein Betriebssystem (Fedora 21) haben.

• Wenn Sie Compiler-Flags oder einen bestimmten Interpreter benötigen, erwähnen Sie dies bitte in Ihrem Beitrag.

Wertung

Ich werde Ihren Code mit 2, 3 usw. Zeichenfolgen ausführen, bis das Drucken einer gültigen Lösung länger als 120 Sekunden dauert. Dies bedeutet, dass Sie für jeden Wert von n 120 Sekunden Zeit haben .

Die höchste Anzahl von Zeichenfolgen, für die Ihr Code rechtzeitig fertiggestellt wurde, ist Ihre Punktzahl.

Bei einem Gleichstand von n wird die Einsendung, die das Problem für n Strings in kürzester Zeit gelöst hat , zum Gewinner erklärt.

Alle Einsendungen werden auf meinem Computer zeitgesteuert (Intel Core i7-3770, 16 GiB RAM, kein Swap).

Die n Zeichenfolgen des (n-1) ^-ten Tests werden durch Aufrufen rand n(und Entfernen der Zeilenvorschübe, falls erforderlich) generiert , wobei randFolgendes definiert ist:

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

Der Schlüssel befindet sich 0im obigen Code, aber ich behalte mir das Recht vor, ihn in einen nicht genannten Wert zu ändern, wenn ich den Verdacht habe, dass jemand die Ausgabe (teilweise) fest codiert.

C, n = 3 in ~ 7 Sekunden

Algorithmus

Der Algorithmus ist eine direkte Verallgemeinerung der Standardlösung für die dynamische Programmierung auf nSequenzen. Für 2 Zeichenfolgen Aund Bsieht die Standardwiederholung folgendermaßen aus:

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

Für 3 - Strings A, B, Cich benutze:

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

Der Code implementiert diese Logik für beliebige Werte von n.

Effizienz

Die Komplexität meines Codes ist O (s ^ n) mit sder Länge der Zeichenfolgen. Basierend auf dem, was ich gefunden habe, sieht es so aus, als ob das Problem NP-vollständig ist. Während der veröffentlichte Algorithmus für größere Werte von sehr ineffizient ist n, ist es möglicherweise nicht möglich, massiv bessere Ergebnisse zu erzielen. Das einzige, was ich gesehen habe, sind einige Ansätze, die die Effizienz kleiner Alphabete verbessern. Da das Alphabet hier mäßig klein ist (16), könnte dies zu einer Verbesserung führen. Ich gehe immer noch davon aus, dass niemand eine legitime Lösung finden wird, die höher als n = 4in 2 Minuten ist und n = 4bereits ehrgeizig aussieht.

Ich habe die Speichernutzung in der ersten Implementierung reduziert, damit sie n = 4genügend Zeit benötigt. Es wurde jedoch nur die Länge der Sequenz erzeugt, nicht die Sequenz selbst. Überprüfen Sie den Versionsverlauf dieses Beitrags, um diesen Code zu sehen.

Code

Da Schleifen über n-dimensionale Matrizen mehr Logik erfordern als feste Schleifen, verwende ich eine feste Schleife für die niedrigste Dimension und verwende nur die generische Schleifenlogik für die verbleibenden Dimensionen.

#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;
}

Anleitung zum Laufen

Laufen:

• Speichern Sie den Code in einer Datei, z lcs.c.

• Kompilieren Sie mit hohen Optimierungsoptionen. Ich benutzte:

  clang -O3 lcs.c
  

  Unter Linux würde ich versuchen:

  gcc -Ofast lcs.c
  

• Führen Sie 2 bis 4 Sequenzen als Befehlszeilenargumente aus:

  ./a.out axbycz xaybzc
  

  Geben Sie bei Bedarf die Befehlszeilenargumente in einfache Anführungszeichen an, da das für die Beispiele verwendete Alphabet Shell-Sonderzeichen enthält.

Ergebnisse

test2.shund test3.shsind die Testsequenzen von Dennis. Ich kenne die richtigen Ergebnisse nicht, aber die Ausgabe sieht zumindest plausibel aus.

$ ./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

Diese Antwort ist derzeit aufgrund eines Fehlers fehlerhaft. Bald behoben ...

C, 2 Saiten in ~ 35 Sekunden

Dies ist eine sehr laufende Arbeit (wie die schreckliche Unordnung zeigt), aber hoffentlich löst sie einige gute Antworten aus!

Der Code:

#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;
}

Die relevante Funktion, die die gesamte LCS-Berechnung ausführt, ist die Funktion LCS. Der obige Code wird einen eigenen Aufruf dieser Funktion zeitlich festlegen.

Speichern unter main.cund kompilieren mit:gcc -Ofast main.c -o FLCS

Der Code kann entweder mit Befehlszeilenargumenten oder über stdin ausgeführt werden. Bei Verwendung von stdin werden mehrere Zeichenfolgen erwartet, gefolgt von den Zeichenfolgen selbst.

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

Oder:

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

Auf einer Mac OS X-Box mit einem 1,7 GHz Intel Core i7 und dem von Dennis bereitgestellten Testfall erhalten wir die folgende Ausgabe für 2 Zeichenfolgen:

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

Der Ansatz ist meinem Ansatz für die frühere Herausforderung hier sehr ähnlich . Zusätzlich zur vorherigen Optimierung überprüfen wir jetzt bei jeder Rekursion die Gesamtzahl der gemeinsam genutzten Zeichen zwischen Zeichenfolgen und beenden sie vorzeitig, wenn es keine Möglichkeit gibt, einen längeren Teilstring als den bereits vorhandenen zu erhalten.

Im Moment verarbeitet es 2 Saiten in Ordnung, neigt aber dazu, bei mehr zum Absturz zu kommen. Weitere Verbesserungen und eine bessere Erklärung folgen!