Наибольший общий делитель строк

По аналогии с числами, у строк тоже может быть свой общий делитель.

Будем считать, что строка t делит строку s, если s можно получить, соединив t саму с собой один или несколько раз (то есть s = t + t + ... + t).

Даны две строки str1 и str2.

Верните самую длинную строку x, которая делит обе строки str1 и str2.

Пример 1:

Ввод: str1 = "ABCABC", str2 = "ABC"
Вывод: "ABC"

Пример 2:

Ввод: str1 = "ABABAB", str2 = "ABAB"
Вывод: "AB"

Пример 3:

Ввод: str1 = "APPLE", str2 = "ORANGE"
Вывод: ""

Ограничения:

• 1 <= str1.length, str2.length <= 1000
• str1 и str2 состоят из заглавных латинских букв.