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$.

The first line of input consists of string

$str1$ of

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

The second line of input consists of string

$str2$ of

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

Output

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

ABCABC ABC

ABC

ABABAB ABAB

AB

ABHCHDBHC AJBDHBCH

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

## Leave a Reply