En este desafío, su tarea es localizar subcadenas con una estructura dada.
Entrada
Su entrada será dos cadenas alfanuméricas no vacías, un patrón p
y un texto t
. La idea es que cada carácter de p
representa una subcadena contigua no vacía t
que ocurre una al lado de la otra, y p
representa su concatenación. Los caracteres idénticos corresponden a subcadenas idénticas; por ejemplo, el patrón aa
representa cualquier cuadrado no vacío (una cadena obtenida mediante la concatenación de una cadena más corta). Por lo tanto, el patrón aa
puede coincidir con la subcadena byebye
, con cada a
coincidencia bye
.
Salida
Si el texto t
contiene una subcadena que p
coincide, entonces su salida será esa subcadena, con dos puntos :
insertados entre las cadenas que corresponden a los caracteres de p
. Por ejemplo, si tenemos t = byebyenow
y p = aa
, entonces bye:bye
es un resultado aceptable. Puede haber varias opciones para la subcadena coincidente, pero solo generará una de ellas.
Si t
no contiene una subcadena coincidente, su salida será una cara triste :(
.
Reglas y aclaraciones
Diferentes caracteres de p
pueden corresponder a subcadenas idénticas, por lo que p = aba
pueden coincidir con la cadena AAA
. Tenga en cuenta que los caracteres deben corresponder a cadenas no vacías; en particular, si p
es más largo que t
, la salida debe ser :(
.
Puede escribir un programa completo o una función, y también puede cambiar el orden de las dos entradas. El conteo de bytes más bajo gana, y las lagunas estándar no se permiten.
Casos de prueba
Dado en el formato pattern text -> output
. Tenga en cuenta que pueden existir otros resultados aceptables.
a Not -> N
aa Not -> :(
abcd Not -> :(
aaa rerere -> re:re:re
xx ABAAAB -> A:A
MMM ABABBAABBAABBA -> ABBA:ABBA:ABBA
x33x 10100110011001 -> 10:1001:1001:10
abcacb 0a00cca0aa0cc0ca0aa0c00c0aaa0c -> c:a0aa:0c:c:0c:a0aa
abccab 0a00cca0aa0cc0ca0aa0c00c0aaa0c -> a:a:0c0:0c0:a:a
abcbcab 0a00cca0aa0cc0ca0aa0c00c0aaa0c -> :(
abcbdcab 0a00cca0aa0cc0ca0aa0c00c0aaa0c -> 00:c:ca0aa0c:c:0:ca0aa0c:00:c
fuente
O(2^((n * (n + 1))/2))
: PRespuestas:
Python, 207 bytes
Llamar con
g(pattern, string)
Utiliza el
re
módulo para hacer la mayor parte del trabajo.fuente
JavaScript (SpiderMonkey) (ES5.1), 198 bytes
Desde que ES6 se lanzó en junio de 2015, publico la versión ES5.1 del código junto con el equivalente ES6, pero declaro la versión ES5.1 como la respuesta principal.
Partido codicioso, por lo que el primer caso devuelve "No" en lugar de "N".
Pruébalo en línea!
JavaScript (Node.js) (ES6), 141 bytes
Pruébalo en línea!
Toma los argumentos en la sintaxis curry:
f(a)(b)
Explicación (y sin golf):
fuente
Brachylog , 35 bytes
Pruébalo en línea!
En entradas no muy pequeñas, muy lentas. Realmente no he hecho el sexto caso de prueba, pero no por falta de intentos lentos. (Probablemente debido a la fuerza bruta de cada partición de cada subcadena, comenzando por la más grande y luego verificando si es una coincidencia). Toma la entrada como una lista
[pattern,string]
.Explicación condensada y dividida:
sᵗ~cᵗX
X es el patrón emparejado con una partición de una subcadena de la cadena de entrada.
lᵛ
El patrón y la partición tienen el mismo número de elementos.
Xzdz≠ʰ
No hay dos
pattern char, matched substring
pares únicos que compartan un carácter de patrón. Es decir, ningún carácter de patrón se asigna a múltiples subcadenas, aunque varios caracteres de patrón pueden asignarse a una subcadena.Xt~ṇ{Ḷ∧":"|}ᵐ.∨":("
La salida son los elementos de la partición unidos por dos puntos, a menos que no se pueda hacer algo, en cuyo caso es en su
:(
lugar.Explicación monolítica:
fuente