GCD of Strings - Algorithm

$1.$ Compute g = gcd(len(str1), len(str2)) using Euclidean algorithm.

$2.$ Extract candidate = str1[0:g] (first g characters).

$3.$ Check if repeating candidate gives both str1 and str2. If yes, return candidate. If no, return empty string.

The check can be done by verifying str1 + str2 == str2 + str1. If that holds, the candidate works.