String LCM (Codeforces 1473B)
Tags: Math, strings

Let's define a multiplication operation between a string $$$a$$$ and a positive integer $$$x$$$: $$$a \cdot x$$$ is the string that is a result of writing $$$x$$$ copies of $$$a$$$ one after another. For example, "abc" $$$\cdot~2~=$$$ "abcabc", "a" $$$\cdot~5~=$$$ "aaaaa".A string $$$a$$$ is divisible by another string $$$b$$$ if there exists an integer $$$x$$$ such that $$$b \cdot x = a$$$. For example, "abababab" is divisible by "ab", but is not divisible by "ababab" or "aa".LCM of two strings $$$s$$$ and $$$t$$$ (defined as $$$LCM(s, t)$$$) is the shortest non-empty string that is divisible by both $$$s$$$ and $$$t$$$.You are given two strings $$$s$$$ and $$$t$$$. Find $$$LCM(s, t)$$$ or report that it does not exist. It can be shown that if $$$LCM(s, t)$$$ exists, it is unique.

Input: The first line contains one integer $$$q$$$ ($$$1 \le q \le 2000$$$) — the number of test cases.Each test case consists of two lines, containing strings $$$s$$$ and $$$t$$$ ($$$1 \le |s|, |t| \le 20$$$). Each character in each of these strings is either 'a' or 'b'.

Output: For each test case, print $$$LCM(s, t)$$$ if it exists; otherwise, print -1. It can be shown that if $$$LCM(s, t)$$$ exists, it is unique.

Note: In the first test case, "baba" = "baba" $$$\cdot~1~=$$$ "ba" $$$\cdot~2$$$.In the second test case, "aaaaaa" = "aa" $$$\cdot~3~=$$$ "aaa" $$$\cdot~2$$$.

Sample Inputs:
3
baba
ba
aa
aaa
aba
ab

Sample Outputs:
baba
aaaaaa
-1

Solution (Python):
import math
num_test_cases = int(input())
for _ in range(num_test_cases):
    s = input()
    t_str = input()
    lcm = ''
    len_s = len(s)
    len_t = len(t_str)
    gcd = len_s * len_t // math.gcd(len_s, len_t)
    lcm_s = s * (gcd // len_s)
    lcm_t = t_str * (gcd // len_t)
    if lcm_s == lcm_t:
        lcm = lcm_s
    print(lcm if lcm else -1)

Solution (Python):
import math
import sys

def myInput():
    return sys.stdin.readline().strip()

def myPrint(string):
    sys.stdout.write(str(string) + '\n')

def factor(x):
    for i in range(2, x):
        if x % i == 0:
            yield i

def hcf(base):
    n_base = len(base)
    if len(set(base)) == 1:
        return base[0]
    else:
        for x in factor(n_base):
            completed = True
            prev = base[0:x]
            for i in range(0, n_base, x):
                if base[i:x + i] != prev:
                    completed = False
                    break
                prev = base[i:x + i]
            if completed:
                return prev
        return base
testcase = int(myInput())
for _ in range(testcase):
    (s, t) = [myInput(), myInput()]
    hcf_s = hcf(s)
    hcf_t = hcf(t)
    if hcf_s == hcf_t:
        myPrint(hcf_t * math.lcm(len(s) // len(hcf_s), len(t) // len(hcf_s)))
    else:
        myPrint(-1)

Solution (Python):
def get_gcd(number1, number2):
    while number2 != 0:
        (number1, number2) = (number2, number1 % number2)
    return number1

def get_lcm(number1, number2):
    return number1 * number2 // get_gcd(number1, number2)
t = int(input())
answer_list = []
while t > 0:
    s = input()
    s2 = input()
    (s, s2) = (min(s, s2), max(s, s2))
    (len_s, len_s2) = (len(s), len(s2))
    if len_s2 % len_s != 0:
        length = get_lcm(len_s, len_s2)
        (s, s2) = (s * (length // len_s), s2 * (length // len_s2))
    else:
        s *= len_s2 // len_s
    if s == s2:
        answer = s
    else:
        answer = -1
    answer_list.append(answer)
    t -= 1
for answer in answer_list:
    print(answer)