¿Qué tan compatibles son mis cadenas?

12

Introducción

Considere dos cadenas A y B de la misma longitud L , y un número entero K ≥ 0 . Para los propósitos de este desafío, decimos que las cadenas son compatibles con K , si existe una cadena C de longitud K tal que A sea ​​una subcadena contigua de la concatenación BCB . Tenga en cuenta que A es una subcadena de BAB , por lo que A y B siempre son compatibles con L (pero también pueden ser compatibles con K para alguna otra K <L ).

Entrada

Sus entradas son dos cadenas de la misma longitud positiva, que consisten en letras ASCII mayúsculas y minúsculas.

Salida

Su salida será el número entero no negativo más bajo K, de modo que las entradas sean compatibles con K.

Ejemplo

Considere las entradas

A = HHHHHH
B = HHttHH

No son compatibles con 0, porque A no es una subcadena de HHttHHHHttHH. Tampoco son compatibles con 1, porque A no es una subcadena HHttHH#HHttHHsin importar qué letra se coloque en el #. Sin embargo, A es una subcadena de HHttHHHHHHttHH, donde C es la cadena de dos letras HH. Por lo tanto, las entradas son compatibles con 2 y la salida correcta es 2.

Reglas y puntaje

Puede escribir un programa completo o una función. El conteo de bytes más bajo gana, y las lagunas estándar no se permiten.

Casos de prueba

La condición de compatibilidad es simétrica, por lo que intercambiar las dos entradas no debería cambiar la salida.

E G -> 1
E E -> 0
aB Bc -> 1
YY tY -> 1
abcd bcda -> 0
abcXd bxcda -> 4
Hello Hello -> 0
Hello olHel -> 1
aBaXYa aXYaBa -> 1
aXYaBa aBaXYa -> 1
HHHHHH HHttHH -> 2
abcdab cdabcd -> 2
XRRXXXXR XRXXRXXR -> 4
evveeetev tetevevev -> 7
vzzvzJvJJz vJJvzJJvJz -> 10
JJfcfJJcfJfb JcfJfbbJJJfJ -> 5
GhhaaHHbbhGGH HHaaHHbbGGGhh -> 9
OyDGqyDGDOGOGyG yDGqOGqDyyyyOyD -> 12
ffKKBBpGfGKpfGpbKb fGpbKbpBBBffbbbffK -> 9
UZuPPZuPdVdtuDdDiuddUPtUidtVVV dtUPtUidtVVVtDZbZZPuiUZuPPZuPd -> 21

Tabla de clasificación

Aquí hay un fragmento de pila para generar una tabla de clasificación y una lista de ganadores por idioma. Para asegurarse de que su respuesta aparezca, comience con un encabezado del formulario

## Language, N bytes

Puede mantener los puntajes antiguos en el encabezado utilizando las etiquetas tachadas: <s>57</s>aparecerá como 57 .

Mostrar fragmento de código

code-golf string Zgarb
fuente

Respuestas:

8

Pyth, 16

lhf}QjT,vzvz+k.:

Encuentre la subcadena más corta de A que cuando se inserta entre dos copias de B da como resultado una cadena que contiene A.

Esto podría ser dos bytes más corto si la segunda línea no tuviera comillas, pero ¿eso se siente raro?

Banco de pruebas

FryAmTheEggman
fuente
4

Python 3, 155 168 157 bytes

Total es la longitud de A. Compare el principio de Ahasta el final de By reste eso del total. Compare el principio de Bhasta el final de Ay reste eso del total. Devuelve el valor absoluto de total a menos que total sea igual a la longitud, en cuyo caso devuelve 0.

def f(A,B):
    T=L=len(A)
    C=D=1
    for i in range(L,0,-1):
        if A[:i]==B[-i:]and C:
            T,C=T-i,0
        if A[-i:]==B[:i]and D:
            T,D=T-i,0
    return (0,abs(T))[T!=-L]

Editar: manejar el f("abcdab","cdabcd")==2caso

Fruta no lineal
fuente
3
Lamentablemente, esto no funciona para lo f("abcdab", "cdabcd")que debería ser 2.
Neil
@Neil Buena captura. Agregaré eso a los casos de prueba.
Zgarb
1
Eso fue inesperado. ( Global Twitch Emotes )
F. George
@ mEQ5aNLrK3lqs3kfSa5HbvsTWe0nIu Estaba mirando la imagen y pensando 'Esta es una ingeniosa idea de depurador para usar emojis, pero no veo un error ...'. Creo que ese complemento causaría estragos en este sitio.
NonlinearFruit
3

Retina , 49 bytes

.*?(?<=^(?=(.*)(?<4-3>.)*(.*) \2.*\1$)(.)*).+
$#4

Pruébalo en línea! (Ligeramente modificado para ejecutar todas las pruebas a la vez).

El truco es que necesitamos retroceder sobre la parte de Alo que no encontramos B, y hasta ahora no he encontrado una manera de hacerlo sin molestos grupos de búsqueda y equilibrio.

Martin Ender
fuente
3

Jolf, 40 bytes

Wά)Ζ0W<ζli)? h++i]Iζ+ζniIoά0nΖhζ}onhn}wn

¡Intentalo!

Soy bastante nuevo en Jolf, aprendí mucho mientras descubría esto. Parece un poco incómodo, aun así, probablemente podría jugar más golf. Incluso eliminó 2 bytes mientras escribía esta explicación.

Explicación:

  Wά)                                      While ά (initialized to 16)
     Ζ0                                    Set ζ to 0
       W<ζli)                              While ζ < length(A)
             ? h++i]Iζ+ζniIoά0n            Set ά to 0 if (A + a substring from B of length n + A) contains B
                               Ζhζ         Increment ζ
                                  }onhn    Increment n (initialize to 0
                                       }wn Decrement n and print
se hincha
fuente
No lo he intentado en serio, y esta puede ser una solución óptima, pero sugiero intentar mapear sobre rangos. ( s0zlile dará una matriz [0 ... longitud i] si desea probar este enfoque.)
Conor O'Brien
@ Cᴏɴᴏʀ O'Bʀɪᴇɴ Hmm, lo echaré un vistazo ... ¿también hay un comando if que omití mientras miraba la documentación / fuente o es la única opción? con un tercer argumento irrelevante?
hincha el
?es el más cercano a un si hay en Jolf. Es como un ternario si. ?ABCs returns B` si a es verdadero, y de lo Ccontrario.
Conor O'Brien
2

JavaScript (ES6), 110 bytes

(a,b)=>{for(i=0;;i++)for(j=i;j<=a.length;j++)if(b.startsWith(a.slice(j))&&b.endsWith(a.slice(0,j-i)))return i}

Funciona cortando piezas cada vez más largas del medio ahasta que coincidan con los dos extremos de b. El bucle no es infinito, ya que se detendrá en o antes i == a.length.

Neil
fuente