If a string t divides both str1 and str2, then the length of t must divide both len(str1) and len(str2). The longest such t has length gcd(len(str1), len(str2)).
Example: len(ABABABAB) = 8, len(ABAB) = 4. gcd(8, 4) = 4. But wait, the answer AB has length 2, not 4. Why?
Because ABAB itself does not divide ABABABAB by simple repetition check. We need to check if the candidate actually works.