Su tarea es resolver el problema de la subsecuencia común más larga para n cadenas de longitud 1000.

Una solución válida al problema LCS para dos o más cadenas S ₁ , ... S _n es cualquier cadena de T de la longitud máxima de tal manera que los personajes de T aparecen en todos los S _i , en el mismo orden que en T .

Tenga en cuenta que T no tiene que ser una subcadena de S _i .

Ya hemos resuelto este problema en la menor cantidad de código . Esta vez, el tamaño no importa.

Ejemplo

Las cadenas axbyczy xaybzctienen 8 subsecuencias comunes de longitud 3:

abc abz ayc ayz xbc xbz xyc xyz

Cualquiera de estos sería una solución válida para el problema de LCS.

Detalles

Escriba un programa completo que resuelva el problema de LCS, como se explicó anteriormente, respetando las siguientes reglas:

• La entrada constará de dos o más cadenas de longitud 1000, que consta de caracteres ASCII con puntos de código entre 0x30 y 0x3F.

• Tienes que leer la entrada de STDIN.

  Tiene dos opciones para el formato de entrada:

  • A cada cadena (incluida la última) le sigue un salto de línea.

  • Las cadenas se encadenan sin separador y sin avance de línea.

• El número de cadenas se pasará como un parámetro de línea de comando a su programa.

• Debe escribir la salida, es decir, cualquiera de las soluciones válidas para el LCS, en STDOUT, seguido de un salto de línea.

• Su idioma de elección debe tener un compilador / intérprete gratuito (como en cerveza) para mi sistema operativo (Fedora 21).

• Si necesita algún indicador de compilación o un intérprete específico, por favor mencionelo en su publicación.

Puntuación

Ejecutaré su código con 2, 3, etc. cadenas hasta que tarde más de 120 segundos en imprimir una solución válida. Esto significa que tiene 120 segundos para cada valor de n .

La mayor cantidad de cadenas para las cuales su código terminó a tiempo es su puntaje.

En el caso de un puntaje empatado de n , la presentación que resolvió el problema para n cadenas en el menor tiempo será declarada ganadora.

Todos los envíos serán programados en mi máquina (Intel Core i7-3770, 16 GiB RAM, sin intercambio).

Los n cuerdas de la (n-1) ^ésimo prueba se generará llamando rand n(y extracción de los avances de línea, si se solicita), donde randse define como sigue:

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

La clave está 0en el código anterior, pero me reservo el derecho de cambiarlo a un valor no revelado si sospecho que alguien está (parcialmente) codificando la salida.

C, n = 3 en ~ 7 segundos

Algoritmo

El algoritmo es una generalización directa de la solución estándar de programación dinámica para nsecuencias. Para 2 cadenas Ay B, la recurrencia estándar se ve así:

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

Por 3 cadenas A, B, Cutilizo:

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

El código implementa esta lógica para valores arbitrarios de n.

Eficiencia

La complejidad de mi código es O (s ^ n), con sla longitud de las cadenas. Según lo que encontré, parece que el problema es NP-completo. Entonces, si bien el algoritmo publicado es muy ineficiente para valores más grandes de n, en realidad podría no ser posible hacerlo enormemente mejor. Lo único que vi son algunos enfoques que mejoran la eficiencia de los alfabetos pequeños. Dado que el alfabeto es moderadamente pequeño aquí (16), eso podría conducir a una mejora. Todavía predigo que nadie encontrará una solución legítima que vaya más alto que n = 4en 2 minutos, y n = 4ya parece ambiciosa.

Reduje el uso de memoria en la implementación inicial, para que pueda manejar n = 4con el tiempo suficiente. Pero solo produjo la longitud de la secuencia, no la secuencia misma. Consulte el historial de revisiones de esta publicación para ver ese código.

Código

Dado que los bucles sobre matrices n-dimensionales requieren más lógica que los bucles fijos, estoy usando un bucle fijo para la dimensión más baja, y solo uso la lógica de bucle genérico para las dimensiones 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;
}

Instrucciones para correr

Correr:

• Guarde el código en un archivo, por ejemplo lcs.c.

• Compile con opciones de alta optimización. Solía:

  clang -O3 lcs.c
  

  En Linux, intentaría:

  gcc -Ofast lcs.c
  

• Ejecutar con 2 a 4 secuencias dadas como argumentos de línea de comando:

  ./a.out axbycz xaybzc
  

  Si es necesario, entre comillas simples los argumentos de la línea de comando, ya que el alfabeto utilizado para los ejemplos contiene caracteres especiales de shell.

Resultados

test2.shy test3.shson las secuencias de prueba de Dennis. No sé los resultados correctos, pero la salida parece al menos 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

Esta respuesta está actualmente rota debido a un error. Arreglando pronto ...

C, 2 cuerdas en ~ 35 segundos

Esto es en gran medida un trabajo en progreso (como lo muestra el horrible desorden), ¡pero espero que genere algunas buenas respuestas!

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

La función relevante que realiza todos los cálculos de LCS es la función LCS. El código anterior cronometrará su propia llamada a esta función.

Guardar como main.cy compilar con:gcc -Ofast main.c -o FLCS

El código se puede ejecutar con argumentos de línea de comando o mediante stdin. Al usar stdin, espera una serie de cadenas seguidas de las propias cadenas.

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

O:

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

En una caja Mac OS X con un Intel Core i7 de 1.7Ghz y el caso de prueba que proporcionó Dennis, obtenemos la siguiente salida para 2 cadenas:

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

El enfoque es muy similar a mi enfoque del desafío anterior, aquí . Además de la optimización anterior, ahora verificamos un número total de caracteres compartidos entre cadenas en cada recursión y salimos temprano si no hay forma de obtener una subcadena más larga de lo que ya existe.

Por ahora, maneja bien 2 cadenas pero tiende a bloquearse más. ¡Más mejoras y una mejor explicación por venir!