Build a Palindrome

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;
	}
}
Ads Blocker Image Powered by Code Help Pro

Ads Blocker Detected!!!

We have detected that you are using extensions to block ads. Please support us by disabling these ads blocker.

Powered By
CHP Adblock Detector Plugin | Codehelppro