LCM of 2 strings

Question

I have to find the LCM of 2 strings given that a multiplication operation exists between a number and a string which dictates that if x is a number and s is a string, then s*x is equal to the string s taken x times.

the strings given are "baba" and "ba". Now I am having trouble even getting started with this because I have to print -1 if the LCM does not exist.

Please help with this. I am just a beginner in c++.

Answer 1

The lcm of the two strings can be found by calculating the lcm of their lengths (Thank you @Damien for this).

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;
}

After you have the lcm of their lengths, then you append each string to itself until the strings are of the same length as the lcm of their lengths.

string StringLCM(string s,int n){
    string result = s;
    for (int i = 0; i < n-1; i++)
    {
        result.append(s);
    }
    return result;
}

THe StringLCM function returns the strings of length equal to the LCM. Now just compare the 2 strings and check if they are equal or not. THe program prints -1 if no LCM can be found. Below is the complete code.

#include<iostream>
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;
}

string StringLCM(string s,int n){
    string result = s;
    for (int i = 0; i < n-1; i++)
    {
        result.append(s);
    }
    return result;
}
 
int main(){
    string s1 = "aba";
    string s2 = "ab";
    int n1= s1.length();
    int n2= s2.length();
    int l=lcm(n1,n2);  
    cout<<l<<endl;
    int flag=0;
    int e =-1;

    s1=StringLCM(s1,l/n1);
    cout<<s1<<endl;
    s2=StringLCM(s2,l/n2);
    cout<<s2<<endl;

    if (s1==s2)
    {
        flag=1;
    }
    if (flag==1)
    {
        cout<<s1<<endl;
    }else
    {
        cout<<e<<endl;
    }
    return 0;
}