QUESTION

You have two strings, a and b. Find a string, s, such that:\n\n 1. s can be expressed as s=sa+sb where sa is a non-empty substring of a and sb is a non-empty substring of b.\n 2. s is a palindromic string.\n3. The length of s is as long as possible.\nFor each of the q pairs of strings ( ai and bi) received as input, find and print string si on a new line. If you’re able to form more than one valid string si, print whichever one comes first alphabetically. If there is no valid answer, print -1 instead.\n\nInput Format\n\nThe first line contains a single integer, q, denoting the number of queries. The subsequent lines describe each query over two lines:\n\n1.The first line contains a single string denoting a.\n2.The second line contains a single string denoting b.\nConstraints\n1.1<=q<=10 2.1<=|a|,|b|<=10^5 3. a and b contain only lowercase English letters. \n4.Sum of |a| over all queries does not exceed 2×10^5\n5. Sum of |b| over all queries does not exceed 2×10^5\nOutput Format\n\nFor each pair of strings ( ai and bi), find some si satisfying the conditions above and print it on a new line. If there is no such string, print -1 instead.

ANSWER

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
#include <map>
#include <set>
#include <string>
#include <cstdlib>
#include <ctime>
#include <deque>
#include <unordered_set>
using namespace std;

#define P 1000000009
int l[410000], s[410000], son[410000][26], parent[410000];
char A[410000], B[410000], AA[410000];
int q;
int len, init, last, LCS[410000], pal[410000], ll[410000], first[410000], mi[410000], ni[410000], Hash[410000];
int ans;
string S1, S2;

int Pow(int x, int y) {
	int ans = 1;
	for (int i = 1; i <= y; i *= 2, x = 1LL * x * x % P)
		if (i & y)
			ans = 1LL * ans * x % P;
	return ans;
}

void ins(int p,int k)
{
	int np=++len,q,nq;
	l[np]=l[p]+1;
	s[np]=1;
	while (p&&!son[p][k])   son[p][k]=np,p=parent[p];
	if (!p) parent[np]=1;
	else {
		q=son[p][k];
		if (l[p]+1==l[q])       parent[np]=q;
		else {
			nq=++len;
			l[nq]=l[p]+1;
			s[nq]=0;
			memcpy(son[nq], son[q], sizeof son[q]);
			parent[nq]=parent[q];
			parent[q]=nq;
			parent[np]=nq;
			while (p&&son[p][k]==q) son[p][k]=nq,p=parent[p];
		}
	}
	last = np;
}

int gethash(int x, int l) {
	return ((Hash[x + l - 1] - Hash[x - 1]) * ni[x] % P + P) % P;
}

bool cmp(char A[210000], int x, int y, int l) {
	for (int i = 0; i < l; i++)
		if (A[x + i] != A[y + i])
			return A[x + i] < A[y + i];
	return false;
	return A[x + q] < A[y + q];
}

string doit(char A[210000], char B[210000]) {
	int n = strlen(A + 1), m = strlen(B + 1);
	last = init=len=1;
	memset(s, 0, sizeof s);
	memset(son, 0, sizeof son);
	memset(parent, 0, sizeof parent);
	memset(l, 0, sizeof l);
	for (int i = 1; i <= m; i++)
		ins(last, B[i] - 'a');
	int now = init, tmp = 0;
	for (int i = 1; i <= n; i++) {
		if (son[now][A[i] - 'a']) {
			now = son[now][A[i] - 'a'];
			tmp += 1;
		}else {
			while (now && !son[now][A[i] - 'a'])
				now = parent[now];
			if (now) {
				tmp = l[now] + 1;
				now = son[now][A[i] - 'a'];
			}else {
				tmp = 0;
				now = init;
			}
		}
		LCS[i] = tmp;
	}

	for (int i = 1; i <= 2 * n + 1; i++)
		AA[i] = '*';
	for (int i = 1; i <= n; i++)
		AA[2 * i] = A[i];
	int best = 2 * n + 1;
	tmp = 2 * n + 1;
	ll[best] = 0;
	first[2 * n + 1] = 2 * n + 1;

	AA[0] = '?';
	AA[2 * n + 2] = '!';

	for (int i = 2 * n; i; i--) {
		ll[i] = 0;
		if (i >= best - ll[best]) {
			ll[i] = min(i - (best - ll[best]), ll[2 * best - i]);
		}
		if (i - ll[i] < best - ll[best])
			best = i;
		while (i - ll[i] < tmp) {
			tmp -= 1;
			first[tmp] = i;
		}
		while (AA[i - ll[i] - 1] == AA[i + ll[i] + 1]) {
			ll[i] += 1;
			if (i - ll[i] < best - ll[best])
				best = i;
			while (i - ll[i] < tmp) {
				tmp -= 1;
				first[tmp] = i;
			}
		}
	}

	for (int i = 1; i <= n; i++) {
		int x = first[2 * i];
		pal[i] = x - (2 * i) + 1;
	}

	pal[n + 1] = 0;
	
	int r = 0;
	for (int i = 1; i <= n; i++)
		if (LCS[i] && (!r || LCS[i] * 2 + pal[i + 1] > LCS[r] * 2 + pal[r + 1]))
			r = i;
	Hash[0] = 0;
	for (int i = 1; i <= n; i++)
		Hash[i] = (Hash[i - 1] + 1LL * (A[i] - 'a') * mi[i]) % 1000000007;
	
	if (!r)
		return "";
	else {
		for (int i = 1; i <= n; i++)
		if (LCS[i] && LCS[i] * 2 + pal[i + 1] == LCS[r] * 2 + pal[r + 1]) {
			if (cmp(A, i - LCS[i] + 1, r - LCS[r] + 1, LCS[r] + (pal[r + 1] + 1) / 2))
				r = i;
		}
		string S = "";
		for (int i = r - LCS[r] + 1; i <= r; i++)
			S.push_back(A[i]);
		for (int i = r + 1; i <= r + pal[r + 1]; i++)
			S.push_back(A[i]);
		for (int i = r; i >= r - LCS[r] + 1; i--)
			S.push_back(A[i]);
		return S;
	}
}

int main() {
	mi[0] = 1;
	for (int i = 1; i <= 200000; i++)
		mi[i] = 1LL * mi[i - 1] * 37 % P;
	ni[0] = 1;
	int kk = Pow(37, P - 2);
	for (int i = 1; i <= 200000; i++)
		ni[i] = 1LL * ni[i - 1] * kk % P;
	scanf("%d", &q);
	while (q--) {
		scanf("%s%s", A + 1, B + 1);
		int n = strlen(A + 1), m = strlen(B + 1);
		
		for (int i = 1; i * 2 <= m; i++)
			swap(B[i], B[m - i + 1]);

		S1 = doit(A, B);
		S2 = doit(B, A);
		if (S1 == "" && S2 == "")
			printf("-1\n");
		else if (S1.size() > S2.size() || (S1.size() == S2.size() && S1 < S2))
			cout << S1 << endl;
		else
			cout << S2 << endl;
	}
}