You are given two strings $a$ and $b$. Determine whether it's possible to swap a prefix from $a$ with a suffix from $b$ such that the two resulting strings are equal.
The prefix and the suffix can be empty and of different lengths.
The first line of the input contains the string $a$ ($1 \leq |a| \leq 5000$).
The second line of the input contains the string $b$ ($1 \leq |b| \leq 5000$).
Both strings consist only of lowercase Latin letters.
If it's possible to make the two strings equal using a single swap, print the final string on a single line. Otherwise, print "-1"(without quotes).
If there are multiple solutions, you can print any of them.
In the first example, we can swap the prefix "bit" from the first string with the suffix "tha" from the second string. Both strings will be equal to "thabit".
| Input | Output |
|---|---|
bitbit thatha Copy
|
thabit Copy
|
burgerburger chickencheese Copy
|
-1 Copy
|
#include <bits/stdc++.h>
using namespace std;
#define f(i, x, n) for (int i = x; i < int(n); ++i)
#define ll long long
int const N = 5000;
char in[N + 1];
string a, b;
int no(){
printf("-1\n");
return 0;
}
int rd(string &s){
scanf("%s", in);
s = in;
return s.size();
}
int main(){
int n = rd(a);
int m = rd(b);
int s = n + m;
if (s & 1)return no();
s >>= 1;
f(i, 0, n){
int need = s - (n - i);
if (need >= 0 && need <= m && b.substr(m - need) + a.substr(i) == b.substr(0, m - need) + a.substr(0, i)){
printf("%s\n", (b.substr(m - need) + a.substr(i)).c_str());
return 0;
}
}
return no();
}