Sua tarefa é resolver o problema de Subseqüência Comum Mais Longa para n seqüências de comprimento 1000.

A solução válida para o problema LCS para duas ou mais cadeias S ₁ , ... S _n é qualquer string T de comprimento máximo de tal forma que os personagens de T aparecer em todos S _i , na mesma ordem como em T .

Note-se que T não tem que ser uma sub seqüência de S _i .

Já resolvemos esse problema na menor quantidade de código . Desta vez, o tamanho não importa.

Exemplo

As cadeias axbycze xaybzctêm 8 subsequências comuns de comprimento 3:

abc abz ayc ayz xbc xbz xyc xyz

Qualquer uma dessas seria uma solução válida para o problema do LCS.

Detalhes

Escreva um programa completo que resolva o problema do LCS, conforme explicado acima, cumprindo as seguintes regras:

• A entrada consistirá em duas ou mais cadeias de comprimento 1000, consistindo em caracteres ASCII com pontos de código entre 0x30 e 0x3F.

• Você precisa ler a entrada de STDIN.

  Você tem duas opções para o formato de entrada:

  • Cada sequência (incluindo a última) é seguida por um avanço de linha.

  • As cadeias são encadeadas sem separador e sem avanço de linha à direita.

• O número de seqüências de caracteres será passado como um parâmetro de linha de comando para o seu programa.

• Você deve escrever a saída, ou seja, qualquer uma das soluções válidas para o LCS, para STDOUT, seguida por um avanço de linha.

• Seu idioma de escolha deve ter um compilador / intérprete gratuito (como na cerveja) para o meu sistema operacional (Fedora 21).

• Se você precisar de sinalizadores de compilador ou de um intérprete específico, mencione-o em sua postagem.

Pontuação

Executarei seu código com 2, 3 etc. seqüências de caracteres até que demore mais de 120 segundos para imprimir uma solução válida. Isso significa que você tem 120 segundos para cada valor de n .

A maior quantidade de strings para as quais seu código terminou no tempo é a sua pontuação.

No caso de uma pontuação empatada de n , a finalização que resolveu o problema de n strings no menor tempo será declarada a vencedora.

Todos os envios serão cronometrados na minha máquina (Intel Core i7-3770, 16 GiB de RAM, sem troca).

As n seqüências do (n-1) ^ésimo teste serão geradas chamando rand n(e eliminando os feeds de linha, se solicitado), onde randé definido da seguinte maneira:

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

A chave está 0no código acima, mas reservo-me o direito de alterá-lo para um valor não revelado se suspeitar que alguém (parcialmente) codifique a saída.

C, n = 3 em ~ 7 segundos

Algoritmo

O algoritmo é uma generalização direta da solução de programação dinâmica padrão para nseqüências. Para 2 strings Ae B, a recorrência padrão é assim:

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

Para 3 cordas A, B, Ceu uso:

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

O código implementa essa lógica para valores arbitrários de n.

Eficiência

A complexidade do meu código é O (s ^ n), com so comprimento das strings. Com base no que descobri, parece que o problema está completo. Portanto, embora o algoritmo publicado seja muito ineficiente para valores maiores de n, talvez não seja possível obter um desempenho massivamente melhor. A única coisa que vi foram algumas abordagens que melhoram a eficiência de pequenos alfabetos. Como o alfabeto é moderadamente pequeno aqui (16), isso poderia levar a uma melhoria. Eu ainda prevejo que ninguém encontrará uma solução legítima que seja mais alta que n = 4em 2 minutos e que n = 4já pareça ambiciosa.

Reduzi o uso de memória na implementação inicial, para que ele pudesse lidar n = 4com tempo suficiente. Mas apenas produziu o comprimento da sequência, não a própria sequência. Verifique o histórico de revisões desta postagem para ver esse código.

Código

Como os loops sobre matrizes n-dimensionais exigem mais lógica do que os loops fixos, estou usando um loop fixo para a dimensão mais baixa e use apenas a lógica de loop genérica para as dimensões 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;
}

Instruções de corrida

Para correr:

• Salve o código em um arquivo, por exemplo lcs.c.

• Compile com opções de alta otimização. Eu usei:

  clang -O3 lcs.c
  

  No Linux, eu tentaria:

  gcc -Ofast lcs.c
  

• Execute com 2 a 4 seqüências fornecidas como argumentos de linha de comando:

  ./a.out axbycz xaybzc
  

  Coloque aspas simples nos argumentos da linha de comando, se necessário, pois o alfabeto usado para os exemplos contém caracteres especiais do shell.

Resultados

test2.she test3.shsão as sequências de teste de Dennis. Não sei os resultados corretos, mas a saída parece pelo menos plausível.

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

Esta resposta está quebrada no momento devido a um erro. A corrigir em breve ...

C, 2 cordas em ~ 35 segundos

Este é um trabalho em andamento (como mostra a horrível confusão), mas espero que acenda algumas boas respostas!

O código:

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

A função relevante que realiza todo o cálculo LCS é a função LCS. O código acima cronometrará sua própria chamada para esta função.

Salvar como main.ce compilar com:gcc -Ofast main.c -o FLCS

O código pode ser executado com argumentos de linha de comando ou através do stdin. Ao usar stdin, espera-se um número de cadeias seguidas pelas próprias cadeias.

~ 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

Em uma caixa do Mac OS X com um Intel Core i7 de 1,7 Ghz e o caso de teste fornecido por Dennis, obtemos a seguinte saída para 2 strings:

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

A abordagem é muito semelhante à minha abordagem ao desafio anterior, aqui . Além da otimização anterior, agora verificamos um número total de caracteres compartilhados entre as strings a cada recursão e saímos mais cedo, se não houver maneira de obter uma substring mais longa do que o que já existe.

Por enquanto, ele lida com duas seqüências de caracteres, mas tende a ficar travado com mais. Mais melhorias e uma melhor explicação para vir!