Smallest string divisible by two given strings | C ++ program for the above approach ; 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 , print - 1 ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; int gcd ( int a , int b ) { if ( b == 0 ) return a ; return gcd ( b , a % b ) ; } int lcm ( int a , int b ) { return ( a / gcd ( a , b ) ) * b ; } void findSmallestString ( string s , string t ) { int n = s . length ( ) , m = t . length ( ) ; int l = lcm ( n , m ) ; string s1 = " " , t1 = " " ; for ( int i = 0 ; i < l / n ; i ++ ) { s1 += s ; } for ( int i = 0 ; i < l / m ; i ++ ) { t1 += t ; } if ( s1 == t1 ) cout << s1 ; else cout << -1 ; } int main ( ) { string S = " baba " , T = " ba " ; findSmallestString ( S , T ) ; return 0 ; }