Su tarea es resolver el problema SLCSC, que consiste en encontrar el código más corto posible para resolver el problema de la subsecuencia común más larga .

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 .

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 o una función que resuelva el problema de LCS, como se explicó anteriormente, respetando las siguientes reglas:

• La entrada constará de dos o más cadenas que contienen solo letras minúsculas.

  Puede leer esas cadenas como una matriz de cadenas o una sola cadena con un delimitador de su elección.

• Su código debe mostrar cualquiera de las posibles soluciones al problema, opcionalmente seguido de un salto de línea o rodeado de comillas.

• Puede suponer que las cadenas tienen menos de 1000 caracteres y que hay como máximo 20 cadenas.

  Dentro de estos límites, su código debería funcionar como se esperaba en teoría (dado tiempo y memoria ilimitados).

• Su código debe completar los casos de prueba combinados de la siguiente sección en menos de una hora en mi máquina (Intel Core i7-3770, 16 GiB RAM).

  Los enfoques que simplemente iteran sobre todas las subsecuencias posibles no cumplirán con el límite de tiempo.

• LongestCommonSequenceNo se permite el uso de elementos integrados que trivializan esta tarea, como por ejemplo .

Se aplican reglas estándar de código de golf .

Casos de prueba

a
ab

Salida: a

aaaaxbbbb
bbbbxcccc
ccccxaaaa

Salida: x

hxbecqibzpyqhosszypghkdddykjfjcajnwfmtfhqcpavqrtoipocijrmqpgzoufkjkyurczxuhkcpehbhpsuieqgjcepuhbpronmlrcgvipvibhuyqndbjbrrzpqbdegmqgjliclcgahxoouqxqpujsyfwbdthteidvigudsuoznykkzskspjufgkhaxorbrdvgodlb
qnnprxqpnafnhekcxljyysobbpyhynvolgtrntqtjpxpchqwgtkpxxvmwwcohxplsailheuzhkbtayvmxnttycdkbdvryjkfhshulptkuarqwuidrnjsydftsyhuueebnrjvkfvhqmyrclehcwethsqzcyfvyohzskvgttggndmdvdgollryqoswviqurrqhiqrqtyrl

Salida: hxbbpyhogntqppcqgkxchpsieuhbncvpuqndbjqmclchqyfttdvgoysuhrrlo cualquier otra subsecuencia común de la misma longitud

riikscwpvsbxrvkpymvbbpmwclizxlhihiubycxmxwviuajdzoonjpkgiuiulbjdpkztsqznhbjhymwzkutmkkkhirryabricvhb
jnrzutfnbqhbaueicsvltalvqoorafnadevojjcsnlftoskhntashydksoheydbeuwlswdzivxnvcrxbgxmquvdnfairsppodznm
kzimnldhqklxyezcuyjaiasaeslicegmnwfavllanoolkhvqkjdvxrsjapqqwnrplcwqginwinktxnkfcuuvoyntrqwwucarfvjg

Salida: icsvllvjnlktywuaro cualquier otra subsecuencia común de la misma longitud

rblartqkfggrjpiipuzzypkycnyckkcqceeujiyy
yfpnedyjtiwrhyuktripdwyvgkblzodeufkelhub
ywcyboxwqkibwvredkrbdsyudkulpvmhixeqxynh
bnxwahbzhwjxkotnvbxrojkkldtsodtjmvdrmbgr

Salida: krkko cualquier otra subsecuencia común de la misma longitud

bwfscmotshoczmduwaev
coywaaizdaxjovipsmeh
dobzcpoiedenzlfdjpiu
bbhfeqscvvbwkuoxdoge
drqrzwbcpcsvneodelja

Salida: codeo cualquier otra subsecuencia común de la misma longitud

nqrualgoedlf
jgqorzglfnpa
fgttvnogldfx
pgostsulyfug
sgnhoyjlnfvr
wdttgkolfkbt

Salida: golfo cualquier otra subsecuencia común de la misma longitud

epopyfuhgowedpiqpgfj
ddxyestqynpwmytxhozm
ptubgzyqqksieoovuezv
tovotqmnhgzttfpywjgr
aomvytkgaijlgqzkljls
vzvxpaixrnprxvenbbuo
syfuwxlpcyontqlmfvib
arxleuomstkjegpduwcx
xgqrxaopouvkvwgbzewn
yggunddigctgpnuztzai
izroomywwztdymqszsuo
kiawjnxjncdtufhkrjsp

Salida: la cadena vacía

CJam, 31

q~L{_:&\f{_2$f#:).>j+}{,}$W>s}j

Pruébalo en línea

¡9 bytes de golf gracias a Dennis!

Explicación:

Este algoritmo prueba todos los caracteres posibles para la primera posición de la subsecuencia, reemplaza cada cadena con la subcadena después de la primera aparición de ese carácter y luego se llama a sí misma de forma recursiva (con memorización).

q~          read and evaluate the input (taken as an array)
L{…}j       execute block with recursive memoization and no starting values
  _         duplicate the array of strings
  :&\       intersect the strings as character sets and move before the array
             these are all the possible characters for the sequence
  f{…}      for each character and the array
    _2$     duplicate the array and the character
    f#      find the character position in each string
    :)      increment the positions (to skip the character)
    .>      slice each string starting at the corresponding position
    j       call the j block recursively
    +       concatenate the starting character with the result
  {,}$      sort resulting strings (one for each character) by length
  W>        keep only the last element, if any
  s         convert (from 0/1-string array) to string

Python - 665 644

Niveles de sangría:

1: space
2: tab
3: tab + space
4: 2 tabs
5: 2 tabs + space

El código define una función o, que toma una lista de cadenas como argumentos y devuelve uno de los LCS para las cadenas.

def o(t):
 t=[[y for y in x if y in reduce(lambda x,y:x.intersection(y),t,set(t[0]))]for x in t];l=map(len,t);C=[0]*reduce(lambda x,y:x*-~y,l,1);y=lambda z:[x-1for x in z];m=len(t);e=enumerate
 def g(h):
    r,x=0,1
    for k,j in e(h):r+=-~j*x;x*=-~l[k]
    return r
 def f(h):
    i=len(h)
    if i==m:
     b=g(h);c=t[0][h[0]]
     for k,j in e(h):
         if t[k][j]!=c:break
     else:C[b]=1+C[g(y(h))];return
     r=0
     for k,_ in e(h):a=h[:];a[k]-=1;r=max(r,C[g(a)])
     C[b]=r;return
    for j,_ in e(t[i]):f(h+[j])
 def p(h):
    if min(h)==-1:return''
    v=C[g(h)]
    for k,_ in e(h):
        a=h[:];a[k]-=1
        if v==C[g(a)]:return p(a)
    return p(y(h))+t[0][h[0]]
 f([]);return p(y(l))

Código de prueba:

tests = [
"""
a
ab
""",
"""
aaaaxbbbb
bbbbxcccc
ccccxaaaa
""",
"""
hxbecqibzpyqhosszypghkdddykjfjcajnwfmtfhqcpavqrtoipocijrmqpgzoufkjkyurczxuhkcpehbhpsuieqgjcepuhbpronmlrcgvipvibhuyqndbjbrrzpqbdegmqgjliclcgahxoouqxqpujsyfwbdthteidvigudsuoznykkzskspjufgkhaxorbrdvgodlb
qnnprxqpnafnhekcxljyysobbpyhynvolgtrntqtjpxpchqwgtkpxxvmwwcohxplsailheuzhkbtayvmxnttycdkbdvryjkfhshulptkuarqwuidrnjsydftsyhuueebnrjvkfvhqmyrclehcwethsqzcyfvyohzskvgttggndmdvdgollryqoswviqurrqhiqrqtyrl
""",
"""
riikscwpvsbxrvkpymvbbpmwclizxlhihiubycxmxwviuajdzoonjpkgiuiulbjdpkztsqznhbjhymwzkutmkkkhirryabricvhb
jnrzutfnbqhbaueicsvltalvqoorafnadevojjcsnlftoskhntashydksoheydbeuwlswdzivxnvcrxbgxmquvdnfairsppodznm
kzimnldhqklxyezcuyjaiasaeslicegmnwfavllanoolkhvqkjdvxrsjapqqwnrplcwqginwinktxnkfcuuvoyntrqwwucarfvjg
""",
"""
rblartqkfggrjpiipuzzypkycnyckkcqceeujiyy
yfpnedyjtiwrhyuktripdwyvgkblzodeufkelhub
ywcyboxwqkibwvredkrbdsyudkulpvmhixeqxynh
bnxwahbzhwjxkotnvbxrojkkldtsodtjmvdrmbgr
""",
"""
bwfscmotshoczmduwaev
coywaaizdaxjovipsmeh
dobzcpoiedenzlfdjpiu
bbhfeqscvvbwkuoxdoge
drqrzwbcpcsvneodelja
""",
"""
nqrualgoedlf
jgqorzglfnpa
fgttvnogldfx
pgostsulyfug
sgnhoyjlnfvr
wdttgkolfkbt
""",
"""
epopyfuhgowedpiqpgfj
ddxyestqynpwmytxhozm
ptubgzyqqksieoovuezv
tovotqmnhgzttfpywjgr
aomvytkgaijlgqzkljls
vzvxpaixrnprxvenbbuo
syfuwxlpcyontqlmfvib
arxleuomstkjegpduwcx
xgqrxaopouvkvwgbzewn
yggunddigctgpnuztzai
izroomywwztdymqszsuo
kiawjnxjncdtufhkrjsp
"""
]

for s in tests:
 print o(s.strip().split())

Tiempo que lleva ejecutar las pruebas en mi computadora:

$ time python 52808-shortest-longest-common-subsequence-code-golfed.py
a
x
hecbpyhogntqtpcqgkxchpsieuhbncvhuqndbjqmclchqyfhtdvgoysuhrrl
icsvllvanlktywuar
krkk
code
golf

        9.03 real         8.99 user         0.03 sys

Pyth, 59 58 55 35 bytes

L&@Fb?+yPMbeeb@FeMbeolNmyXJbdP@bdlb

¡Corta la friolera de 20 bytes gracias a @isaacg!

Versión de 55 bytes:

DCHR?k!&.AH@FH?+Cm<1dHeeHql{medH1h.MlZ.eC++<Hk]<1b>HhkH

Corte 3 bytes cambiando .U@bZa @F(el operador de plegado).

Versión de 58 bytes:

DCHR?k!&.AH.U@bZH?+Cm<1dHeeHql{medH1h.MlZ.eC++<Hk]<1b>HhkH

Corte un byte cambiando el formato de un condicional booleano.

Versión de 59 bytes:

DCHR?k|!.AH!.U@bZH?+Cm<1dHeeHql{medH1h.MlZ.eC++<Hk]<1b>HhkH

Esto fue dificil! Python siguió segfaulting! Estoy bastante seguro de que fue algún tipo de error, pero no pude obtener un caso de prueba mínimo. Oh bien.

Basé el algoritmo en este . Lo cual está bien, excepto que ese está diseñado para solo dos cadenas. Tuve que ajustarlo un poco para que funcione más. Luego, el último caso de prueba tardó demasiado, así que tuve que agregar una verificación adicional para salir de la recursividad si no hay más caracteres comunes.

Es bastante lento, pero debería tomar menos de una hora (con suerte). Estoy probando en mi Core i3 con 6 GB de RAM, por lo que su Core i7 de 16 GB debería superar esto. :)

También aproveché las funciones de auto-memorización de Pyth para hacerlo un poco más rápido.

EDITAR : @Dennis dijo que pasa!

Para probarlo, agregue la siguiente línea:

CQ

y darle una lista de cadenas a través de la entrada estándar (por ejemplo ['a', 'ab']).

Explicación para la versión de 35 bytes:

WIP

Explicación para la versión de 55 bytes:

DCH                                                        define a function C that takes a list of strings H
   R                                                       return the following expression
    ?                                                      if
      !&.AH@FH                                             there are no more common letters OR all the strings are empty
     k                                                     return the empty string
              ?          ql{medH1                          else if the last character of every string is equal
               +Cm<1dHeeH                                  return the result of adding the last character to recursion with every item without its last character
                                 h.MlZ.eC++<Hk]<1b>HhkH    otherwise, return the largest result of recursing len(H) times, each time with one element's last character cut off

C, 618 564 bytes

d,M,N,A[9999][2];char*(R[9999][20]),b[1000];L(char**s,n){char*j[20],c,a=0;int x[n],y=n-1,z,i,t,m=0,w=1;for(;y;)x[y--]=999;for(;y<N;y++){for(i=0;i<n&&s[i]==R[y][i];i++);if(i/n){a=A[y][0];m=A[y][1];w=0;if(m+d<M||!a)goto J;else{c=a;goto K;}}}for(c=97;w&&c<'{';c++){K:t=1,y=1,z=1;for(i=0;i<n;j[i++]++){for(j[i]=s[i];*j[i]-c;j[i]++)t&=!!*j[i];y&=j[i]-s[i]>x[i]?z=0,1:0;}t&=!y;I:if(t){if(z)for(i=0;i<n;i++)x[i]=j[i]-s[i];d++,t+=L(j,n),d--,m=t>m?a=c,t:m;}}if(w){for(y=0;y<n;y++)R[N][y]=s[y];A[N][0]=a;A[N++][1]=m;}J:if(d+m>=M)M=d+m,b[d]=a;if(!d)N=0,M=0,puts(b);return m;}

Y aquí está descifrado, por "legibilidad":

d,M,N,A[9999][2];
char*(R[9999][20]),b[1000];
L(char**s,n){
    char*j[20],c,a=0;
    int x[n],y=n-1,z,i,t,m=0,w=1;
    for(;y;)
        x[y--]=999;
    for(;y<N;y++){
        for(i=0;i<n&&s[i]==R[y][i];i++);
        if(i/n){
            a=A[y][0];
            m=A[y][1];
            w=0;
            if(m+d<M||!a)
                goto J;
            else{
                c=a;
                goto K;
            }
        }
    }
    for(c=97;w&&c<'{';c++){
        K:
        t=1,
        y=1,
        z=1;
        for(i=0;i<n;j[i++]++){
            for(j[i]=s[i];*j[i]-c;j[i]++)
                t&=!!*j[i];
            y&=j[i]-s[i]>x[i]?z=0,1:0;
        }
        t&=!y;
        I:
        if(t){
            if(z)
                for(i=0;i<n;i++)
                    x[i]=j[i]-s[i];
            d++,
            t+=L(j,n),
            d--,
            m=t>m?a=c,t:m;
        }
    }
    if(w){
        for(y=0;y<n;y++)R[N][y]=s[y];
        A[N][0]=a;
        A[N++][1]=m;
    }
    J:
    if(d+m>=M)
        M=d+m,b[d]=a;
    if(!d)
        N=0,M=0,puts(b);
    return m;
}

Damas y caballeros, he cometido un error horrible. Se utiliza para ser más bonita ... y Goto-menos ... Al menos ahora es rápida .

Definimos una función recursiva Lque toma como entrada una matriz sde matrices de caracteres y el número nde cadenas. La función genera la cadena resultante en stdout y, por cierto, devuelve el tamaño en caracteres de esa cadena.

El enfoque

Aunque el código es complicado, la estrategia aquí no es demasiado compleja. Comenzamos con un algoritmo recursivo bastante ingenuo, que describiré con pseudocódigo:

Function L (array of strings s, number of strings n), returns length:

Create array of strings j of size n;

For each character c in "a-z",
    For each integer i less than n,
         Set the i'th string of j to the i'th string of s, starting at the first appearance of c in s[i]. (e.g. j[i][0] == c)
         If c does not occur in the i'th string of s, continue on to the next c.
    end For

    new_length := L( j, n ) + 1; // (C) t = new_length
    if new_length > best_length
        best_character := c; // (C) a = best_character
        best_length := new_length; // (C) m = best_length
    end if
end For

// (C) d = current_depth_in_recursion_tree
if best_length + current_depth_in_recursion_tree >= best_found
     prepend best_character to output_string // (C) b = output_string
     // (C) M = best_found, which represents the longest common substring found at any given point in the execution.
     best_found = best_length + current_depth;
end if

if current_depth_in_recursion_tree == 0
    reset all variables, print output_string
end if 

return best_length

Ahora, este algoritmo por sí solo es bastante atroz (pero he encontrado unos 230 bytes). No es así como se obtienen resultados rápidos. Este algoritmo escala increíblemente mal con la longitud de la cadena. Este algoritmo tiene , sin embargo, la escala bastante bien con un mayor número de cadenas. El último caso de prueba se resolvería prácticamente al instante, ya que las cadenas no stienen ningún carácter cen común. Hubo dos trucos principales que implementé anteriormente que resultaron en un increíble aumento de velocidad:

• En cada llamada a L, verifique si se nos ha dado esta misma entrada antes. Como en la práctica la información se transmite a través de punteros al mismo conjunto de cadenas, en realidad no tenemos que comparar cadenas, solo ubicaciones, lo cual es genial. Si descubrimos que obtuvimos esta información antes, no hay necesidad de ejecutar los cálculos (la mayoría de las veces, pero obtener resultados hace que esto sea un poco más complicado) y podemos salir con solo devolver la longitud. Si no encontramos una coincidencia, guarde este conjunto de entrada / salida para compararlo con futuras llamadas. En el código C, el segundo forciclo intenta encontrar coincidencias con la entrada. Los punteros de entrada conocidos se guardan Ry los valores de salida de caracteres y longitud correspondientes se almacenan enA. Este plan tuvo un efecto drástico en el tiempo de ejecución, especialmente con cadenas más largas.

• Cada vez que encontramos las ubicaciones de cin s, existe la posibilidad de que sepamos de inmediato que lo que hemos encontrado no es óptimo. Si cada ubicación de caparece después de alguna ubicación conocida de otra letra, sabemos automáticamente que esto cno conduce a una subcadena óptima, porque puede incluir una letra más en ella. Esto significa que por un pequeño costo, potencialmente podemos eliminar varios cientos de llamadas a Lcadenas grandes. En el código C anterior, yhay un conjunto de indicadores si sabemos automáticamente que este carácter conduce a una cadena subóptima, y zes un conjunto de indicadores si encontramos un carácter que tiene apariencias exclusivamente anteriores a cualquier otro carácter conocido. Las primeras apariencias actuales de los personajes se almacenan enx. La implementación actual de esta idea es un poco desordenada, pero casi duplica el rendimiento en muchos casos.

Con estas dos ideas, lo que no terminó en una hora ahora tomó alrededor de 0.015 segundos.

Probablemente hay muchos más trucos que pueden acelerar el rendimiento, pero en este punto comencé a preocuparme por mi capacidad para jugar golf todo. Todavía no estoy contento con el golf, ¡así que probablemente volveré a esto más tarde!

Tiempos

Aquí hay un código de prueba, que te invito a probar en línea :

#include "stdio.h"
#include "time.h"

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

int main(int argc, char** argv) {
    /* Our test case */
    char* test7[] = {
        "nqrualgoedlf",
        "jgqorzglfnpa",
        "fgttvnogldfx",
        "pgostsulyfug",
        "sgnhoyjlnfvr",
        "wdttgkolfkbt"
    };

    printf("Test 7:\n\t");
    clock_t start = clock();

    /* The call to L */
    int size = L(test7, SIZE_ARRAY(test7));


    double dt = ((double)(clock() - start)) / CLOCKS_PER_SEC;
    printf("\tSize: %d\n", size);
    printf("\tElapsed time: %lf s\n", dt);

    return 0;
}

Ejecuté los casos de prueba del OP en una computadora portátil equipada con un chip Intel Core i7 de 1.7 GHz, con una configuración de optimización de -Ofast. La simulación informó un pico de 712 KB requerido. Aquí hay un ejemplo de cada caso de prueba, con tiempos:

Test 1:
    a
    Size: 1
    Elapsed time: 0.000020 s
Test 2:
    x
    Size: 1
    Elapsed time: 0.000017 s
Test 3:
    hecbpyhogntqppcqgkxchpsieuhbmcbhuqdjbrqmclchqyfhtdvdoysuhrrl
    Size: 60
    Elapsed time: 0.054547 s
Test 4:
    ihicvaoodsnktkrar
    Size: 17
    Elapsed time: 0.007459 s
Test 5:
    krkk
    Size: 4
    Elapsed time: 0.000051 s
Test 6:
    code
    Size: 4
    Elapsed time: 0.000045 s
Test 7:
    golf
    Size: 4
    Elapsed time: 0.000040 s
Test 8:

    Size: 0
    Elapsed time: 0.000029 s


Total time: 0.062293 s

En el golf, alcancé el rendimiento de manera bastante significativa, y dado que a la gente parecía gustarle la velocidad bruta (0.013624 s para completar todos los casos de prueba combinados) de mi solución anterior de 618 bytes, lo dejaré aquí como referencia:

d,M,N,A[9999][2];char*(R[9999][20]),b[1000];L(char**s,n){char*j[20],c,a=0;int x[n],y,z,i,t,m=0,w=1;for(y=0;y<n;y++)x[y]=999;for(y=0;y<N;y++){for(i=0;i<n;i++)if(s[i]!=R[y][i])break;if(i==n){a=A[y][0];m=A[y][1];w=0;if(m+d<M||!a)goto J;else{c=a;goto K;}}}for(c=97;w&&c<'{';c++){K:t=1,y=1,z=1;for(i=0;i<n;j[i++]++){for(j[i]=s[i];*j[i]-c;j[i]++)if(!*j[i]){t=0;goto I;}if(j[i]-s[i]>x[i])z=0;if(j[i]-s[i]<x[i])y=0;}if(y){t=0;}I:if(t){if(z){for(i=0;i<n;i++){x[i]=j[i]-s[i];}}d++,t+=L(j,n),d--,m=t>m?(a=c),t:m;}}if(w){for(y=0;y<n;y++)R[N][y]=s[y];A[N][0]=a;A[N++][1]=m;}J:if(d+m>=M)M=d+m,b[d]=a;if(!d)N=0,M=0,puts(b);return m;}

El algoritmo en sí no ha cambiado, pero el nuevo código se basa en divisiones y algunas operaciones bit a bit más complicadas que terminan ralentizando todo.

Pitón 2, 285

Código:

import re
def f(s,a,b):
  if b==[]:return s+f('',[],a)
  if a==[]:return s+max([f(b[0][i],[b[0][i+1:]],b[1:]) for i in range(len(b[0]))],key=len) if b[0]!='' else ''
  return max([f(s,a+[b[0][i.start()+1:]],b[1:]) for i in re.finditer(s[-1],b[0])],key=len) if ~b[0].find(s[-1]) else ''

Uso:

print f('',[],['axbycz','xaybzc'])

Explicación:

Esta es una función recursiva. ses el personaje que estamos buscando. acontiene una lista de cadenas cortadas después s. bcontiene una lista de cadenas sin tocar todavía. fdevuelve la cadena común más larga.

La primera condición verifica si hemos terminado de pasar por todas las cadenas. si es así, significa que ses un carácter común, y regresa sy busca caracteres más comunes.

La segunda condición verifica si no comenzamos a pasar por ninguna cadena, lo que significa que ni siquiera tenemos un carácter ( a==[]es equivalente a s==''). si es así, verificamos cada carácter de la primera cadena b.

La última línea mueve la primera cadena bhacia adentro a, al encontrar cada aparición de sen esta cadena.

En la primera llamada, sdebe ser una cadena vacía. adebe estar lista vacía y bdebe contener todas las cadenas.