Máximo común divisor de strings
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
Si existe un divisor común t, ambos strings están hechos de copias de t. ¿Qué pasa cuando pegas los dos strings en cualquiera de los dos órdenes?
a + b es igual a b + a exactamente cuando ambos strings están construidos con la misma unidad. Si los dos son distintos, la respuesta es vacía.
Cuando a + b == b + a, el divisor común más largo tiene longitud gcd(len(a), len(b)), y es simplemente el prefijo de a con esa longitud.
- Tiempo objetivo
- O(len(a) + len(b))
- Espacio objetivo
- O(len(a) + len(b))
Solución
Si ambos strings son copias de alguna unidad t, entonces a + b y b + a son la misma cantidad de copias de t, así que son iguales; si los strings no están construidos con una unidad común, las dos concatenaciones difieren en algún punto, y esa única comparación descarta el caso. Cuando sí comparten una unidad, todo divisor común tiene una longitud que divide a ambas longitudes, y la longitud más grande posible, el máximo común divisor (MCD) de las dos longitudes, también funciona, ya que un prefijo de esa longitud cubre exactamente ambos strings. El algoritmo de Euclides lo calcula en O(log n) pasos, así que la solución cuesta O(n + m) de tiempo por la comprobación de la concatenación y O(n + m) de espacio.
from math import gcd
def gcd_of_strings(a, b):
if a + b != b + a: # no common building block exists
return ""
return a[:gcd(len(a), len(b))] # the longest block that tiles both
print(gcd_of_strings("ABCABC", "ABC")) # -> ABC
print(gcd_of_strings("ABABAB", "ABAB")) # -> AB
print(gcd_of_strings("LOOP", "POOL")) # -> (empty string)¿Lo que te frena es la idea y no el código? MCD y Euclides lo explica.