Smallest string divisible by two given strings | Function to calculate GCD of two numbers ; Function to calculate LCM of two numbers ; Function to find the smallest string which is divisible by strings S and T ; Store the length of both strings ; Store LCM of n and m ; Temporary strings to store concatenated strings ; Concatenate s1 ( l / n ) times ; Concatenate t1 ( l / m ) times ; If s1 and t1 are equal ; Otherwise , pr - 1 ; Driver Code
def gcd ( a , b ) : NEW_LINE INDENT if ( b == 0 ) : NEW_LINE INDENT return a NEW_LINE DEDENT return gcd ( b , a % b ) NEW_LINE DEDENT def lcm ( a , b ) : NEW_LINE INDENT return ( a // gcd ( a , b ) ) * b NEW_LINE DEDENT def findSmallestString ( s , t ) : NEW_LINE INDENT n , m = len ( s ) , len ( t ) NEW_LINE l = lcm ( n , m ) NEW_LINE s1 , t1 = " " , " " NEW_LINE for i in range ( l // n ) : NEW_LINE INDENT s1 += s NEW_LINE DEDENT for i in range ( l // m ) : NEW_LINE INDENT t1 += t NEW_LINE DEDENT if ( s1 == t1 ) : NEW_LINE INDENT print ( s1 ) NEW_LINE DEDENT else : NEW_LINE INDENT print ( - 1 ) NEW_LINE DEDENT DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT S , T = " baba " , " ba " NEW_LINE findSmallestString ( S , T ) NEW_LINE DEDENT