Source Code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define REP(n) for (ll _loop = 0; _loop < n; _loop++)
#define RRIP(i,z,n) for(ll i = n-1; i >= z; i--)
#define RIP(i,l,n) for (ll i = l; i < n; i++)
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define B begin()
#define E end()
#define ln '\n'
const ll INF64 = 3e18;
const int mod = (int)1e9 + 7;
//const int mod = 998244353;
const int MAX_N = 100000 + 5;
ll binp(ll a, ll b)
{	if (b == 0)
		return 1;
	ll ans = binp(a, b/2);
	ll tmp = (ans * ans);
	if (b % 2)return ((tmp * a));
		return ((tmp));
}
ll mbinp(ll a, ll b)
{
	a %= mod;
	if (b == 0)
		return 1;
	ll ans = mbinp(a, b/2);
	ll tmp = (ans * ans) % mod;
	if (b % 2)
		return ((tmp * a) % mod);
	return ((tmp) % mod);
}

void display(vector<int> v)
{
	for (auto x : v)
		cout << x << " ";
	cout << "\n";
}
ll gcd(ll a, ll b) {
	if (b == 0) 
		return a;
	return gcd(b, a%b);
}



void here(ll a)
{
	cout << "here " << a << endl;
}

// ll _sieve_size;
// bitset<100000010> bs;
// vector<ll> primes;

// void sieve(ll upperbound) 
// {
// 	_sieve_size = upperbound + 1;
// 	bs.set();
// 	bs[0] = bs[1] = 0;
// 	for (ll i = 2; i <= _sieve_size; i++) if (bs[i]) {
// 		for (ll j = i * i; j <= _sieve_size; j += i) bs[j] = 0;
// 			primes.push_back((int)i);
// 	}
// }

// bool isPrime(ll N) {
// 	if (N <= _sieve_size) return bs[N];
// 	for (int i = 0; i < (int)primes.size(); i++)
// 		if (N % primes[i] == 0) return false;
// 	return true;
// }

// set<pair<ll, ll>> primeFactors(ll N) {
// 	set<pair<ll,ll>> factors;
// 	ll PF_idx = 0, PF = primes[PF_idx];
// 	while (PF * PF <= N) 
// 	{
// 		ll pow = 0;
// 		bool fac = false;
// 		while (N % PF == 0) { fac = true; N /= PF; pow++;}
// 		factors.insert(mp(PF, pow));
// 		PF = primes[++PF_idx];
// 	}
// 	if (N != 1) factors.insert(mp(N, 1));
// 	return factors;
// }

// const ll nmax = (ll)1e6 + 1;
// //ll adj[nmax][nmax];
// ll par[nmax];
// ll siize[nmax];

// ll find(ll x)
// {
// 	if (par[x] == x)
// 		return x;
// 	return par[x] = find(par[x]);
// }

// void merge(ll a, ll b)
// {
// 	ll x = find(a);
// 	ll y = find(b);
// 	if (x == y)
// 		return;
// 	ll sizex = siize[x];
// 	ll sizey = siize[y];
// 	if (sizex < sizey)
// 	{
// 		par[x] = par[y];
// 		siize[y] += siize[x];
// 	}
// 	else
// 	{
// 		par[y] = par[x];
// 		siize[x] += siize[y];
// 	}
// }

// const ll nmax = 300002;
//vector<ll> adj[nmax];
//queue<ll> q
// bool vis[nmax];

ll numlen(ll n)
{
	ll ret = 1;
	while (n >= 10)
	{
		n /= 10;
		ret++;
	}
	return ret;
}


// const int xmax = 200002;
// vector<ll> adj[xmax];
// vector<bool> vis(xmax);
// vector<ll> dp(xmax);
// vector<int> a(xmax);

// ll	dfs(ll u)
// {
// 	if (vis[u])
// 		return 0;
// 	vis[u] = true;
// 	dp[u] = a[u];
// 	for (auto x : adj[u])
// 		dp[u] += max(dfs(x), (ll)0);
// 	return dp[u];
// }

// struct segmentTree{
// 	ll len;
// 	vector<ll> op;

// 	void init(ll n)
// 	{
// 		len = 1;
// 		while (len < n) len *= 2;
// 		// initialize with neutral element for operation
// 		op.assign(2*len, 0);
// 	}

// 	void build(vector<ll> &arr, ll x, ll lx, ll rx, ll n)
// 	{
// 		if (rx - lx == 1)
// 		{
// 			if (lx < n)
// 				op[x] = arr[lx];
// 			return;
// 		}
// 		ll mid = (lx + rx) / 2;
// 		build(arr, 2*x+1, lx, mid, n);
// 		build(arr, 2*x+2, mid, rx, n);
// 		// initialize value from values of left and right subtrees
// 		op[x] = max(op[2*x+1],op[2*x+2]);
// 	}

// 	void build(vector<ll> &arr, ll n)
// 	{
// 		build(arr, 0, 0, len, n);
// 	}

// 	void set(ll i, ll v, ll x, ll lx, ll rx)
// 	{
// 		if (rx - lx == 1)
// 		{
// 			op[x] = v;
// 			return;
// 		}
// 		ll mid = (lx + rx) / 2;
// 		if (i < mid)
// 			set(i, v, 2*x+1, lx, mid);
// 		else
// 			set(i, v, 2*x+2, mid, rx);
// 		// get new value by appling op to left and right subtrees
// 		op[x] = max(op[2*x+1],op[2*x+2]);
// 	}

// 	void set(ll i, ll v)
// 	{
// 		set(i, v, 0, 0, len);
// 	}

// 	ll get(ll l, ll r, ll x, ll lx, ll rx)
// 	{
// 		if (lx >= r || l >= rx)
// 			return 0; // neutral element for the operation
// 		if (lx >= l && rx <= r)
// 			return op[x];
// 		ll mid = (lx + rx) / 2;
// 		ll get1 = get(l, r, 2*x+1, lx, mid);
// 		ll get2 = get(l, r, 2*x+2, mid, rx);
// 		// return op of left and right subtrees
// 		return max(get1,get2);
// 	}

// 	ll get(ll l, ll r)
// 	{
// 		return get(l, r, 0, 0, len);
// 	}
// };


// const ll maxchar = 1024;
// vector<vector<char>> arr(maxchar, vector<char>(maxchar, '.'));

// struct rec{
// 	ll id;
// 	ll x1;
// 	ll y1;
// 	ll x2;
// 	ll y2;

// 	void recInit(ll a, ll b, ll c, ll d)
// 	{
// 		x1 = a;
// 		y1 = b;
// 		x2 = c;
// 		y2 = d;
// 	}

// 	bool recInside(rec &w)
// 	{
// 		return (x1 >= w.x1 && y1 >= w.y1 && y2 <= w.y2 && x2 <= w.x2);
// 	}

// 	bool recOutside(rec &w)
// 	{
// 		return (x1 > w.x2 || y1 > w.y2 || w.x1 > x2 || w.y1 > y2);
// 	}
// };

// char c;

// struct squareTree{
// 	ll nbc;
// 	vector<ll> nbt;
// 	const ll maxs = 400000;
// 	ll n;

// 	void init(ll m)
// 	{relocation truncated to fit: R_X86_64_PC32 against symbol `par' defined in .bss section in /tmp/cc74aPA
// 		n = 1;
// 		while (n < m) n *= 2;
// 		ll spow = log(n*n)/log(4) + 1;
// 		nbc = (binp(4, spow) - 1)/3;
// 		nbt.assign(nbc, 0);
// 	}

// 	void build(rec &z)
// 	{
// 		if (z.x1 == z.x2 && z.y1 == z.y2)
// 		{
// 			if (z.x1 < n && z.y1 < n)
// 				nbt[z.id] = (arr[z.x1][z.y1] == '*')? 1 : 0;
// 			return;
// 		}
// 		rec a, b, c, d;
// 		a.recInit(z.x1, z.y1, (z.x1+z.x2)/2, (z.y1+z.y2)/2);
// 		a.id = 4*z.id + 1;
// 		build(a);
// 		b.recInit(z.x1, (z.y1+z.y2)/2 + 1, (z.x1+z.x2)/2, z.y2);
// 		b.id = 4*z.id + 2;
// 		build(b);
// 		c.recInit((z.x1+z.x2)/2 + 1, z.y1, z.x2, (z.y1+z.y2)/2);
// 		c.id = 4*z.id + 3;
// 		build(c);
// 		d.recInit((z.x1+z.x2)/2 + 1, (z.y1+z.y2)/2 + 1, z.x2, z.y2);
// 		d.id = 4*z.id + 4;
// 		build(d);
// 		nbt[z.id] = nbt[a.id] + nbt[b.id] + nbt[c.id] + nbt[d.id];
// 	}

// 	void build()
// 	{
// 		rec forest;
// 		forest.recInit(0,0,n-1, n-1);
// 		forest.id = 0;
// 		build(forest);
// 	}

// 	ll get(rec &k, rec &z)
// 	{
// 		if (z.recInside(k))
// 		{
// 			return nbt[z.id];
// 		}
// 		if (z.recOutside(k))
// 		{
// 			return 0;
// 		}
// 		rec a, b, c, d;
// 		a.recInit(z.x1, z.y1, (z.x1+z.x2)/2, (z.y1+z.y2)/2);
// 		a.id = 4*z.id + 1;
// 		ll get1 = get(k, a);
// 		b.recInit(z.x1, (z.y1+z.y2)/2 + 1, (z.x1+z.x2)/2, z.y2);
// 		b.id = 4*z.id + 2;
// 		ll get2 = get(k, b);
// 		c.recInit((z.x1+z.x2)/2 + 1, z.y1, z.x2, (z.y1+z.y2)/2);
// 		c.id = 4*z.id + 3;
// 		ll get3 = get(k, c);
// 		d.recInit((z.x1+z.x2)/2 + 1, (z.y1+z.y2)/2 + 1, z.x2, z.y2);
// 		d.id = 4*z.id + 4;
// 		ll get4 = get(k, d);
// 		return get1 + get2 + get3 + get4;
// 	}

// 	ll get(rec &k)
// 	{
// 		rec forest;
// 		forest.recInit(0,0,n-1, n-1);
// 		forest.id = 0;
// 		return get(k, forest);
// 	}
// };

// void	bfsdist(ll s, ll n, vector<vector<pair<ll,ll>>> &adj, vector<ll> &distS)
// {
// 	distS.assign(n, INF64);
// 	priority_queue<pair<ll,ll>> q;
// 	distS[s] = 0;
// 	q.push(mp(0,s));
// 	vector<bool> vis(n);
// 	while (!q.empty())
// 	{
// 		ll a = q.top().S; q.pop();
// 		if (vis[a]) continue;
// 		vis[a] = true;
// 		for (auto u : adj[a])
// 		{
// 			ll b = u.F;
// 			ll w = u.S;
// 			if (distS[a]+w < distS[b]) 
// 			{
// 				distS[b] = distS[a]+w;
// 				q.push(mp(-distS[b],b));
// 			}
// 		}
// 	}
// }

// void permute(string a, int l, int r) 
// { 
//     if (l == r) 
//         cout << a << endl; 
//     else
//     { 
//         for (int i = l; i <= r; i++) 
//         { 
//             swap(a[l], a[i]); 
//             permute(a, l+1, r); 
//             swap(a[l], a[i]); 
//         } 
//     } 
// }

// ll dfs(vector<vector<ll>> &adj, vector<bool> &vis, vector<ll> &v, ll i)
// {
// 	if (vis[i])
// 		return INF64;
// 	vis[i] = true;
// 	ll mini = INF64;
// 	for (auto x : adj[i])
// 	{
// 		mini = min(min(mini,v[x]), dfs(adj, vis, v, x));
// 	}
// 	return mini;
// }

// struct segmentTree{
// 	ll len;
// 	vector<ll> op;
// 	ll prevmax;
 
// 	ll init(ll n)
// 	{
// 		len = 1;
// 		while (len < n) len *= 2;
// 		// initialize with neutral element for operation
// 		op.assign(len*2, 0);
// 		return len;
// 	}
 
// 	void build(vector<ll> &arr, ll x, ll lx, ll rx, ll n)
// 	{
// 		if (rx - lx == 1)
// 		{
// 			if (lx < n)
// 				op[x] = arr[lx];
// 			return;
// 		}
// 		ll mid = (lx + rx) / 2;			vector<ll> sum;
// 		build(arr, 2*x+1, lx, mid, n);
// 		build(arr, 2*x+2, mid, rx, n);
// 		// initialize value from values of left and right subtrees
// 		op[x] = max(op[2*x+1],op[2*x+2]);
// 	}
 
// 	void build(vector<ll> &arr, ll n)
// 	{
// 		build(arr, 0, 0, len, n);
// 	}
 
// 	void set(ll i, ll v, ll x, ll lx, ll rx)
// 	{
// 		if (rx - lx == 1)
// 		{
// 			op[x] = v;
// 			return;
// 		}
// 		ll mid = (lx + rx) / 2;
// 		if (i < mid)
// 			set(i, v, 2*x+1, lx, mid);
// 		else
// 			set(i, v, 2*x+2, mid, rx);
// 		// get new value by appling op to left and right subtrees
// 		op[x] = max(op[2*x+1], op[2*x+2]);
// 	}
 
// 	void set(ll i, ll v)
// 	{
// 		set(i, v, 0, 0, len);
// 	}
 
// 	ll get(ll nb, vector<ll> &disc)
// 	{
// 		ll x = 0, l = 0, r = len;
// 		if (op[x] < nb)
// 			return -1;
// 		while (r-l!=1)
// 		{
// 			ll mid = (l + r) / 2;
// 			if (op[2*x+1] >= nb)
// 			{
// 				x = 2*x+1; 
// 				r = mid;
// 			}
// 			else if (op[2*x+2] >= nb)
// 			{
// 				x = 2*x+2;
// 				l = mid;
// 			}
// 		}
// 		return (l);
// 	}
// };


void qr(ll i, ll j)
{
	cout << "? " << i << " " << j << ln;
	cout.flush();
}

void display2(vector<vector<ll>> &v)
{
	for (auto x : v)
	{
		for (auto y : x)
			cout << y << " ";
		cout << ln;
	}
}

void bfsdist(vector<vector<ll>> &adj, vector<ll> &dist, ll i, ll n)
{
	vector<bool> vis(n);
	queue<ll> q;
	dist[i] = 0;
	vis[i] = true;
	q.push(i);
	while (!q.empty())
	{
		ll w = q.front();
		q.pop();
		for (auto z : adj[w])
		{
			if (vis[z]) continue;
			vis[z] = true;
			dist[z] = dist[w] + 1;
			q.push(z);
		}
	}
}

vector<int> z(string s) {
	int n = s.size();
	vector<int> z(n);
	int x = 0, y = 0;
	for (int i = 1; i < n; i++) 
	{
		z[i] = max(0,min(z[i-x],y-i+1));
		while (i+z[i] < n && s[z[i]] == s[i+z[i]]) 
		{
			x = i;
			y = i+z[i];
			z[i]++;
		}
	}
	return z;
}

int main()
{
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

	//freopen("test_input.txt", "r", stdin);
	// freopen("string.out", "w", stdout);

	string a;
	string b;
	cin >> a;
	cin >> b;
	ll na = a.size();
	ll nb = b.size();
	string reva = a;
	reverse(reva.B, reva.E);
	vector<int> zreva = z(reva);
	vector<int> zb = z(b);
	//display(zreva);
	//display(zb);
	ll maxib = max_element(zb.B, zb.E) - zb.B;
	ll maxia = max_element(zreva.B, zreva.E) - zreva.B;
	if (maxia == 0)
		maxia = na;
	if (maxib == 0)
		maxib = nb;
	string newa = b.substr(maxib) + a.substr(na-maxia);
	string newb = b.substr(0, maxib) + a.substr(0, na-maxia);
	//cout << newa << " " << newb << ln;
	if (newa == newb)
		cout << newa << ln;
	else
		cout << -1 << ln;
}
Copy
Right into Two sigma
GNU G++17
0 ms
492 KB
Wrong Answer