Saltar al contenido

Máximo común divisor de strings

Fácil#gcd#string-period~15 min

La misión

Problema

Un string (cadena) t divide a un string s cuando s es t escrito una o más veces seguidas. Dados dos strings a y b, devuelve el string más largo que divide a ambos, o un string vacío cuando ningún string los divide.

Ejemplos

Input:  a = "ABCABC", b = "ABC"
Output: "ABC"
Input:  a = "ABABAB", b = "ABAB"
Output: "AB"
Por qué: AB divide a ambos, mientras que ABAB no divide a ABABAB
Input:  a = "LOOP", b = "POOL"
Output: ""
Por qué: caso límite: los strings no comparten ninguna unidad que se repita

Pistas

0 / 3

Tiempo objetivo
O(len(a) + len(b))
Espacio objetivo
O(len(a) + len(b))

¿Lo que te frena es la idea y no el código? MCD y Euclides lo explica.

Python 3Ctrl+Enter ejecuta
Caso de prueba propio