CF 1326D Prefix-Suffix Palindrome(最长回文前后缀)

Problem - D2 - Codeforces

大意：给出一个字符串 S ， 找出满足以下条件的字符串 T。

1. 字符串 T 尽可能长 并且 |T| ≤ |S|

2.字符串 T 由 S 的一个前缀和后缀拼接而成 ， T 是回文串。

思路：思考如何表示字符串 T

如图所示 ， 可以表示成上图的形式(对应位置想同颜色即为相同字母) ，而且这样表示一定是最优的（可以证明） ， 所以可以先暴力枚举 S 中前后相等的部分 ， 然后对剩余部分取得最长的公共前缀/后缀即可。

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define int long long
const int N = 2e6 + 10;
const int mod = 1e9 + 7;
typedef pair<int,int>PII;

string s;
int t , n;

/*

abcdeffedcba

bc abcdeed cba

*/

int d[N] , pre[N] , nex[N];
//给出一个字符串求d[i]数组并返回马拉车串
string manacher(string s){
	
	string now = "#$";
	int n = s.size();
	for(int i = 0 ; i < n ; i ++) now += s[i] , now += '$';
	n = now.size();
	for(int i = 0 ; i < n ; i ++) pre[i] = nex[i] = i;
	d[1] = 1;
	for(int i = 2 , l , r = 1; i < n ; i ++){
		if(i <= r) d[i] = min(d[r - i + l] , r - i + 1);
		else d[i] = 1;
		while(now[i - d[i]] == now[i + d[i]]){
			d[i] += 1;
			pre[i + d[i] - 1] = i - d[i] + 1;
			nex[i - d[i] + 1] = i + d[i] - 1;
		}
		if(i + d[i] - 1 > r) l = i - d[i] + 1 , r = i + d[i] - 1; 	
	}
	return now;	
}

void watch(string s){
	int n = s.size();
	for(int i = 0 ; i < n ; i ++) cout << s[i] << " ";
	cout << "\n"; 
	for(int i = 0 ; i < n ; i ++) cout << d[i] << " ";
	cout << "\n";
}

signed main(){

	IOS
	cin >> t;
	
	while(t --){
		cin >> s;
		int n = s.size() , st = 0;
		while(st < n && s[st] == s[n - st - 1] && st < n - st - 1) st += 1;
		string a , b , c;
		for(int i = 0 ; i < st ; i ++) a += s[i];
		for(int i = n - st ; i < n ; i ++) b += s[i];
		for(int i = st ; i < n - st ; i ++) c += s[i];
		
		string mid;
		
		if(c.size()){
			string now = manacher(c);
	//		watch(now);
			n = now.size() - 2;
			int x = ((nex[2] - 2 + 1) + 1) / 2;
			int y = ((n - pre[n] + 1) + 1) / 2;
			n = c.size();
			if(x >= y){
				for(int i = 0 ; i < x ; i ++) mid += c[i];
			}else{
				for(int i = n - y ; i < n ; i ++) mid += c[i];
			}
		}
			
		string ans = a + mid + b;
		cout << ans << "\n";
	}

	return 0;
}
//freopen("文件名.in","r",stdin);
//freopen("文件名.out","w",stdout);