Divisible Strings DSA Problem Solution

Posted by admin July 25, 2023
Divisible Strings DSA Problem Solution
Divisible Strings DSA Problem Solution

In this post, we are going to solve Divisible Strings DSA Problem from Flipkart Online assessment. Let’s have a look at the problem statement first and then try to solve the problem.

Divisible Strings DSA Problem Statement

For two strings

S and

T, we say “T divides S” if and only if

S =

T + … +

T (i.e.,

T is concatenated with itself one or more times).

Given two strings

str1 and

str2, return the largest string

x such that

x divides both

str1 and

str2.

Input

The first line of input consists of string

str1 of

104≤size≤104 and consisting of uppercase latin letters only

The second line of input consists of string

str2 of

104≤size≤104 and consisting of uppercase latin letters only

Output

Output

x as described in the statement and if the answer does not exist you can output empty string.

Examples
Input
ABCABC
ABC
Output
ABC
Input
ABABAB
ABAB
Output
AB
Input
ABHCHDBHC
AJBDHBCH
Output
Problem Solution in C++
#include <bits/stdc++.h>
using namespace std;

int main() {

string s,t;
cin>>s>>t;
int x=__gcd(s.size(),t.size());

if(s+t!=t+s)
{
cout<<"";
}
else
cout<<t.substr(0,x);

return 0;

}