Cree un programa o función que tome una lista de cadenas como entrada y genere la cadena más larga que es una subcadena de todas las cadenas de entrada. Si hay varias subcadenas de igual longitud y ya no son más, envíe cualquiera de ellas.
- Esto puede significar la salida de la cadena vacía.
- Si hay varias salidas válidas, puede generar cualquiera de ellas. No es necesario que proporcione resultados consistentes para una entrada dada siempre que la salida sea siempre válida.
- Siempre habrá al menos una cadena en la entrada, pero puede que no haya una cadena no vacía.
- Todos los caracteres ASCII imprimibles pueden aparecer en la entrada. Puede suponer que esos son los únicos personajes que aparecen.
- Puede tomar entrada o producir salida por cualquiera de los métodos predeterminados .
- Las lagunas estándar no están permitidas.
- Este es el código de golf : cuantos menos bytes de código, mejor.
Casos de prueba:
[Inputs] -> [Valid outputs (choose one)]
["hello", "'ello"] -> ["ello"]
["very", "much", "different"] -> [""]
["empty", "", "STRING"] -> [""]
["identical", "identical"] -> ["identical"]
["string", "stRIng"] -> ["st", "ng"]
["this one", "is a substring of this one"] -> ["this one"]
["just one"] -> ["just one"]
["", "", ""] -> [""]
["many outputs", "stuptuo ynam"] -> ["m", "a", "n", "y", " ", "o", "u", "t", "p", "s"]
["many inputs", "any inputs", "ny iii", "yanny"] -> ["ny"]
["%%not&", "ju&#st", "[&]alpha_numeric"] -> ["&"]
code-golf
string
subsequence
Sara J
fuente
fuente
undefined
implica que no hay una cadena de salida válida. Si la cadena vacía (o cualquier otra cadena) es una salida válida, afirmar que no hay salida válida es incorrecta.Respuestas:
Python 2 , 82 bytes
Pruébalo en línea!
Toma entrada salpicada. Tiempo de espera para entradas donde la primera cadena es larga.
La idea es tomar subcadenas de las primeras cadenas
h
para encontrar la más larga que aparece en todas las cadenas restantest
. Para hacerlo, recurrimos recursivamente al eliminar el primer o el último carácter deh
.Python 2 , 94 bytes
Pruébalo en línea!
Un método más directo. La función auxiliar
g
genera el conjunto de todas las subcadenass
, y la función principal toma la más larga en su intersección.fuente
Brachylog (v2),
39 bytesPruébalo en línea!
Programa completo Entrada desde entrada estándar (como una lista de cadenas de estilo JSON), salida a salida estándar.
Explicación
Aparentemente, el orden de desempate
s
no es el que está en casi todo lo demás en Brachylog, por lo que debemos anularlo manualmente para producir la salida más larga. (Eso es un poco frustrante: cuatro caracteres adicionales para la anulación, más dos caracteres de agrupación porque Brachylog no analiza dos metapredicados seguidos).Brachylog's
s
no devuelve subcadenas vacías, por lo que necesitamos un poco de truco para evitarlo: en lugar de hacer una presentación de función (que es lo que normalmente se hace), escribimos un programa completo, que sale a la salida estándar. De esa manera, si hay una subcadena común, simplemente la sacamos y terminamos. Si no hay una subcadena común, el programa produce errores, pero aún no imprime nada en la salida estándar, por lo tanto, genera la cadena nula como se esperaba.fuente
s
incorrecto, y anular el orden de desempate es bastante costoso en bytes. Sin embargo, hacer eso ahora de todos modos, porque es importante que la respuesta sea correcta. De alguna manera, ninguno de los casos de prueba que probé notó la diferencia.s
produce subcadenas es primero dando todos los prefijos de la entrada (los más largos primero), luego soltando el primero y repitiendoJalea ,
126 bytesPruébalo en línea!
¡Gracias a @JonathanAllan por guardar 6 bytes!
fuente
Ẇ€œ&/Ṫḟ0
que haría el trabajo y ahorraría cuatro bytes ya que las subcadenas ya están ordenadas por longitud, por lo tanto, el resultado filtrado será; entonces todo lo que queda es que cuando no hay coincidencias, la cola produce un cero, y dado que tenemos listas de caracteres garantizadas, simplemente podemos filtrarlas.œ&/
puede ser sustituido porf/
aquí ahorro de otraẆ€f/ṛ/
.Ruby 2.6,
76 5954 bytesPruébalo en línea! - Versión Ruby 2.5 (56 bytes)
¿Cómo?
Cree una lista de posibles coincidencias, inicialmente configurada en la matriz original. Itere en la lista, y si una cadena no coincide, agregue 2 nuevas cadenas a la cola de la lista, cortando el primer o el último carácter. Al final se encontrará una coincidencia (eventualmente una cadena vacía).
Gracias Kirill L por -2 bytes y histocrat por otro -2
fuente
R ,
119116108106 bytesPruébalo en línea!
Encuentre todas las subcadenas de cada cadena, encuentre la intersección de cada lista de subcadenas, y finalmente devuelva (una de) las más largas.
-3 bytes gracias a Kirill L.
-8 bytes usando en
lapply
lugar deMap
-2 bytes gracias a Kirill L. nuevamente, quitando llaves
fuente
nchar
son suficientes para guardar algo al declararmenchar
como un operador unario.list
manera similar nos da -3 bytes.05AB1E ,
1498 bytes-6 bytes gracias a @Adnan .
Pruébelo en línea o verifique todos los casos de prueba .
Explicación:
fuente
€Œ.«Ãõªéθ
debería funcionar para 9 bytes.Å«Ã
, pero no me di cuenta de que debería haberlo usado.«Ã
. ¡Gracias!€Œ.«ÃéθJ
debería funcionar para 8.Zsh ,
126 ...96 bytes-3 bytes de aritmética para, -6 bytes de implícito
"$@"
(gracias roblogic), -5 bytes de eliminación innecesaria{
}
, -1 byte de forma abreviadafor
, -1 byte usandorepeat
, -1 byte concatenandofor s ($b)
con su cuerpo, -13 bytes cambiando el ciclo de repetición para algunos jank evalPruébalo en línea! Pruébalo en línea!Pruébalo en línea!Leemos todas las posibles subcadenas en la matriz
a
y luego establecemosb
la intersección de las matricesa
yb
. La construcción${b-$a}
solo sustituirá$a
en la primera iteración: a diferencia de su expansión entre hermanos${b:-$a}
, no sustituirá cuandob
se establece sino que está vacía.fuente
a+=( $l[1+i/$#l,1+i%$#l] )
for
bucles anidadosfor l in "$@"
simplementefor l;
: es un truco bashb=(${${b-$a}:*a})}
man zshexpn
yman zshparam
sobre todo. Siempre los tengo abiertos cuando escribo una respuesta.Haskell , 80 bytes
Pruébalo en línea!
Obtener todos los sufijos (
tails
) de la primera palabrax
en la lista y tomar todos los prefijos (inits
) de esos sufijos para obtener todas las subcadenass
dex
. Mantenga cada unos
que lasisInfixOf
all
cuerdas en la lista restanter
. Ordenar esas subcadenas por longitud (usando el(0<$)
truco ) y devuelve la última.fuente
Retina 0.8.2 , 48 bytes
Pruébalo en línea! Explicación:
Para cada sufijo de la primera cadena, encuentre el prefijo más largo que también sea una subcadena de todas las otras cadenas. Enumere todos esos prefijos de sufijo (es decir, subcadenas). Si no hay subcadenas coincidentes, simplemente terminamos con la cadena vacía, que es lo que queremos de todos modos.
Ordenar las subcadenas en orden inverso de longitud.
Mantenga solo la primera, es decir, la subcadena más larga.
fuente
n
es el número de cadenas de argumentos. Entonces(?=(.*\n.*\1)*.*$)
debería ser(?=(.*\n.*\1){n-1}.*$)
, ¿no? Caso de prueba:["very", "different", "much"] -> [""]
{n}
usted podría eliminar los patrones de inicio y finalización y mantenerlos(.+)(?=(.*\n.*\1){n}
si Retina permite escribirn
más corto que(?<=^.*).*$
Consulta TSQL, 154 bytes
Pruébalo en línea
Se distingue entre mayúsculas y minúsculas al declarar la columna 'a' con clasificación que contiene CS (mayúsculas y minúsculas).
Dividiendo todas las cadenas de 2540 posiciones iniciales (muchas idénticas) pero los valores útiles oscilan entre 1 y 2070 y terminando de 0 a 22 caracteres después de la posición inicial, la posición final podría ser más larga cambiando el tipo a 'P' en lugar de 'L', pero paralizaría el rendimiento.
Se cuentan estas cadenas distintas dentro de cada número de rown. El conteo más alto siempre será igual al número de filas en la variable de tabla '@'. Revertir el orden en el mismo recuento dejará la subcadena con la mayoría de las coincidencias en la parte superior de los resultados, seguido de la longitud inversa de la subcadena, dejará la coincidencia más larga con la mayoría de las coincidencias en la parte superior. La consulta solo selecciona la 1 fila superior.
Para obtener todas las respuestas, cambie la primera parte de la consulta a
fuente
C # (Visual C # interactivo Compilador),
320257 bytesPruébalo en línea!
Atrezzo a @Expired Data y @dana
fuente
Perl 6 ,
6260 bytesPruébalo en línea!
Estoy un poco molesto porque Perl 6 no puede establecer operaciones en listas de listas, por eso hay un extra
.comb
y>>
allí.Otra cosa molesta es queComo se señaló en los comentarios,max
no puede tomar una función de cómo comparar elementos, lo que significa que tengo que usarsort
en su lugar.max
puede tomar un argumento, sin embargo, termina más tiempo ya que tengo que tener en cuenta quemax
devuelve el infinito negativo cuando hay subcadenas comunes (¡ Pruébelo en línea! ).fuente
max
puede tomar dicha función (arity 1 sin embargo), ya sea por posición cuando se llama en modo OO, o un:by
argumento con nombre en modo de procedimiento.Japt v2.0a0
-hF
, 8 bytesGracias a Shaggy por guardar 3 bytes.
Intentalo
fuente
-F
predeterminado es la cadena vacía.Japt
-h
, 8 bytes(Podría eliminar los últimos 3 bytes y usar la
-Fh
bandera en su lugar, pero no soy fanático de usar-F
)Pruébalo o ejecuta todos los casos de prueba
fuente
Python 3 , 137 bytes
Pruébalo en línea!
fuente
Python 2 , 103 bytes
Pruébalo en línea!
Esta es una lambda anónima que transforma cada elemento en el conjunto de todas las subcadenas, luego
reduce
lo establece mediante la intersección establecida (set.__and__
) y luego devuelve elmax
elemento porlen
gth.fuente
set.intersection
.C # (compilador interactivo de Visual C #) ,
147145bytesPruébalo en línea!
fuente
Perl 5 (
-aln0777F/\n/
-M5.01
-MList::util=max
), 99 bytesse puede jugar más golf
TIO
fuente
JavaScript (ES6),
9892 bytesPruébalo en línea!
fuente
Carbón , 30 bytes
Pruébalo en línea! El enlace es a la versión detallada del código. Este algoritmo es más eficiente y más corto que generar todas las subcadenas. Explicación:
Haga estallar la última cadena de la lista de entrada en una variable.
Ponga a cero el índice de inicio de la subcadena.
Recorra todos los índices finales de subcadenas posibles. (En realidad, esto se repite desde 0 excluyendo la longitud, por lo que el valor se ajusta más adelante)
Obtenga la subcadena actual.
Compruebe si esta subcadena está contenida en todas las demás cadenas de entrada.
Si se sobreimprime cualquier subcadena de salida anterior.
De lo contrario, intente incrementar el índice de inicio de la subcadena.
fuente
Bash ,
295.. 175 bytesNo es bonito pero al menos funciona. Pruébalo en línea
-37 por limpieza general ; -52 plagiando de la respuesta zsh ; -26 reemplazando la matriz con un bucle ; -2 gracias a GammaFunction ; -3 eliminado
i=0
delfor
bucleAquí está el guión original sin comentarios con comentarios
fuente
((k==$#))&&
con((k-$#))||
. Esto también le permite usarlo enk=
lugar de establecerlo en 0.Rojo ,
266174bytesPruébalo en línea!
Cambió la recursión a iteración y se deshizo de la clasificación.
fuente
Perl 5 , 87 bytes
Pruébalo en línea!
fuente
JavaScript (Node.js) , 106 bytes
Pruébalo en línea!
fuente
Gaia , 15 bytes
Pruébalo en línea!
fuente
PowerShell ,
16516387 bytes-76 bytes gracias a Nail por la increíble expresión regular .
Pruébalo en línea!
Menos golfizado:
fuente
JavaScript (Node.js) , 90 bytes
Pruébalo en línea! Casos de prueba robados descaradamente de @Arnauld. Puerto de mi respuesta de carbón.
fuente
Java (JDK) , 158 bytes
Pruébalo en línea!
Créditos
fuente
Perl 5 , 86 bytes
Pruébalo en línea!
fuente
Pyth , 16 bytes
Pruébalo en línea!
fuente