# 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$$S$ and

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

$S$$S$ =

$T$$T$ + … +

$T$$T$ (i.e.,

$T$$T$ is concatenated with itself one or more times).

Given two strings

$str1$$str1$ and

$str2$$str2$, return the largest string

$x$$x$ such that

$x$$x$ divides both

$str1$$str1$ and

$str2$$str2$.

Input

The first line of input consists of string

$str1$$str1$ of

${10}^{4}\le size\le {10}^{4}$$10^{4}\le size \le 10^{4}$ and consisting of uppercase latin letters only

The second line of input consists of string

$str2$$str2$ of

${10}^{4}\le size\le {10}^{4}$$10^{4}\le size \le 10^{4}$ and consisting of uppercase latin letters only

Output

Output

$x$$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;

}