Votre tâche consiste à résoudre le problème de la séquence la plus longue commune pour n chaînes de longueur 1000.

Une solution valable au problème LCS pour deux ou plusieurs chaînes de ₁ , ... S _n est une chaîne T de longueur maximale telle que les caractères de T apparaissent dans tous les S _i , dans le même ordre que dans T .

Notez que T ne doit pas nécessairement être une sous- chaîne de S _i .

Nous avons déjà résolu ce problème dans la quantité de code la plus courte . Cette fois, la taille n'a pas d'importance.

Exemple

Les chaînes axbyczet xaybzcont 8 sous-séquences communes de longueur 3:

abc abz ayc ayz xbc xbz xyc xyz

N'importe lequel d'entre eux serait une solution valable pour le problème LCS.

Détails

Écrivez un programme complet qui résout le problème LCS, comme expliqué ci-dessus, en respectant les règles suivantes:

• L'entrée consistera en deux ou plusieurs chaînes de longueur 1000, composées de caractères ASCII avec des points de code compris entre 0x30 et 0x3F.

• Vous devez lire l'entrée de STDIN.

  Vous avez deux choix pour le format d'entrée:

  • Chaque chaîne (y compris la dernière) est suivie d'un saut de ligne.

  • Les chaînes sont enchaînées sans séparateur ni saut de ligne arrière.

• Le nombre de chaînes sera transmis en tant que paramètre de ligne de commande à votre programme.

• Vous devez écrire la sortie, c'est-à-dire l'une des solutions valides du LCS, dans STDOUT, suivie d'un saut de ligne.

• Votre langue de choix doit avoir un compilateur / interprète gratuit (comme dans la bière) pour mon système d'exploitation (Fedora 21).

• Si vous avez besoin de drapeaux de compilation ou d'un interprète spécifique, veuillez le mentionner dans votre message.

Notation

Je vais exécuter votre code avec 2, 3, etc. chaînes jusqu'à ce qu'il prenne plus de 120 secondes pour imprimer une solution valide. Cela signifie que vous disposez de 120 secondes pour chaque valeur de n .

Le nombre le plus élevé de chaînes pour lesquelles votre code s'est terminé dans le temps est votre score.

En cas d'égalité de n , la soumission ayant résolu le problème pour n chaînes dans les plus brefs délais sera déclarée gagnante.

Toutes les soumissions seront chronométrées sur ma machine (Intel Core i7-3770, 16 Go de RAM, pas de swap).

Les n chaînes du (n-1) ^e test seront générées en appelant rand n(et en supprimant les sauts de ligne, si demandé), où randest défini comme suit:

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

La clé est 0dans le code ci-dessus, mais je me réserve le droit de la changer en une valeur non divulguée si je soupçonne quelqu'un de coder en dur (partiellement) la sortie.

C, n = 3 en ~ 7 secondes

Algorithme

L'algorithme est une généralisation directe de la solution de programmation dynamique standard aux nséquences. Pour 2 chaînes Aet B, la récurrence standard ressemble à ceci:

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

Pour 3 cordes A, B, Cje l' utilise:

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

Le code implémente cette logique pour les valeurs arbitraires de n.

Efficacité

La complexité de mon code est O (s ^ n), avec sla longueur des chaînes. D'après ce que j'ai trouvé, il semble que le problème soit NP-complet. Ainsi, bien que l'algorithme affiché soit très inefficace pour des valeurs plus grandes de n, il pourrait en fait ne pas être possible de faire beaucoup mieux. La seule chose que j'ai vue, ce sont des approches qui améliorent l'efficacité des petits alphabets. Puisque l'alphabet est modérément petit ici (16), cela pourrait conduire à une amélioration. Je prédis toujours que personne ne trouvera une solution légitime qui va plus haut qu'en n = 42 minutes et qui n = 4a déjà l'air ambitieuse.

J'ai réduit l'utilisation de la mémoire dans l'implémentation initiale, afin qu'elle puisse gérer n = 4suffisamment de temps. Mais cela n'a produit que la longueur de la séquence, pas la séquence elle-même. Consultez l'historique des révisions de ce message pour voir ce code.

Code

Étant donné que les boucles sur des matrices à n dimensions nécessitent plus de logique que les boucles fixes, j'utilise une boucle fixe pour la dimension la plus basse et n'utilise la logique de boucle générique que pour les dimensions restantes.

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

Instructions pour courir

Courir:

• Enregistrez le code dans un fichier, par exemple lcs.c.

• Compilez avec des options d'optimisation élevées. J'ai utilisé:

  clang -O3 lcs.c
  

  Sous Linux, j'essaierais:

  gcc -Ofast lcs.c
  

• Exécutez avec 2 à 4 séquences données comme arguments de ligne de commande:

  ./a.out axbycz xaybzc
  

  Citez les arguments de la ligne de commande si nécessaire, car l'alphabet utilisé pour les exemples contient des caractères spéciaux shell.

Résultats

test2.shet test3.shsont les séquences de test de Dennis. Je ne connais pas les résultats corrects, mais la sortie semble au moins plausible.

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

Cette réponse est actuellement interrompue en raison d'un bogue. Correction bientôt ...

C, 2 cordes en ~ 35 secondes

C'est vraiment un travail en cours (comme le montre l'horrible désordre), mais j'espère que cela suscitera de bonnes réponses!

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

La fonction pertinente qui effectue tout le calcul LCS est la fonction LCS. Le code ci-dessus chronomètre son propre appel à cette fonction.

Enregistrez sous main.cet compilez avec:gcc -Ofast main.c -o FLCS

Le code peut être exécuté avec des arguments de ligne de commande ou via stdin. Lors de l'utilisation de stdin, il attend un certain nombre de chaînes suivies des chaînes elles-mêmes.

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

Ou:

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

Sur un boîtier Mac OS X avec un Intel Core i7 1,7 GHz et le scénario de test fourni par Dennis, nous obtenons la sortie suivante pour 2 chaînes:

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

L'approche est très similaire à mon approche du défi précédent, ici . En plus de l'optimisation précédente, nous vérifions maintenant le nombre total de caractères partagés entre les chaînes à chaque récursivité et sortons tôt s'il n'y a aucun moyen d'obtenir une sous-chaîne plus longue que celle qui existe déjà.

Pour l'instant, il gère bien 2 chaînes mais a tendance à se bloquer plus. Plus d'améliorations et une meilleure explication à venir!