Greatest Common Divisor of Strings
Problem
A string t divides a string s when s is t written one or more times in a row. Given two strings a and b, return the longest string that divides both of them, or an empty string when no string does.
Examples
Input: a = "ABCABC", b = "ABC"
Output: "ABC"Input: a = "ABABAB", b = "ABAB"
Output: "AB"
Why: AB divides both, while ABAB does not divide ABABABInput: a = "LOOP", b = "POOL"
Output: ""
Why: edge case, the strings share no repeating unit at allHints
0 / 3
If a common divisor t exists, both strings are made of copies of t. What happens when you glue the two strings together in either order?
a + b equals b + a exactly when both strings are built from the same unit. If the two differ, the answer is empty.
When a + b == b + a, the longest common divisor has length gcd(len(a), len(b)), and it is simply the prefix of a with that length.
Solution
If both strings are copies of some unit t, then a + b and b + a are the same number of copies of t, so they are equal; if the strings are not built from a common unit, the two concatenations differ somewhere, and that one comparison rules the case out. When they do share a unit, every common divisor has a length that divides both lengths, and the longest possible length, the greatest common divisor of the two lengths, also works, since a prefix of that length tiles both strings. Euclid's algorithm computes it in O(log n) steps, so the whole solution costs O(n + m) time for the concatenation check and O(n + m) space.
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)Stuck on the idea rather than the code? GCD and Euclid covers it.