Codeforces Global Round 7 cf 1326D 马拉车

题意是叫你找最长的回文串，然后这个回文串可以由原本的串的前驱+后继拼起来。

由于前驱和后继是必须选的对不对（可能有一个为空）。
那么我们第一步就是吧原本的串倒置，把正的和反的去找出最长的相同的，这样就满足了前驱+后继的限制。下一步是什么？

假设原本的长度是[1,len]，我们上面找到的最长相同的长度是3，那么就是接下来剩下的串就是[1 + 3 - 1 , len - 3],剩下的这一段我们只需要找到两个端点为开头的最长回文串就好了。如图所示。

为什么是两个端点？如果选取了左端点则说明我们与前驱的串接上去了。如果选择了右端点，这说明我们与后继的串接上去了。这样就满足了题意。要求这个的长度我用了马拉车。复杂度是O(N)，所以这道题也就解决了。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#include<time.h>
#include<string>
#include<cmath>
#include<stack>
#include<map>
#include<set>
#define int long long
#define double long double
using namespace std;
#define PI 3.1415926535898
#define eqs 1e-10
const long long max_ = 1e6 + 7;
const int mod = 998244353;
const int inf = 1e9 + 7;
const long long INF = 1e18;
int read() {
	int s = 0, f = 1;
	char ch = getchar();
	while (ch<'0' || ch>'9') {
		if (ch == '-')
			f = -1;
		ch = getchar();
	}
	while (ch >= '0'&&ch <= '9') {
		s = s * 10 + ch - '0';
		ch = getchar();
	}
	return s * f;
}
inline int min(int a, int b) {
	return a < b ? a : b;
}
inline int max(int a, int b) {
	return a > b ? a : b;
}
int nn = 1, pr[max_ * 2], weizhi, extralen = -1;
char node[2 * max_],yuan[max_];
void dr(int L,int R) {
	nn = 1; extralen = -1;
	node[0] = '~';
	node[1] = '|';
	for(int i = L;i <= R;i++) {
		node[++nn] = yuan[i];
		node[++nn] = '|';
	}
	int mid = 0, maxr = 0;
	for (int i = 1; i <= nn; i++) {
		if (i <= maxr && i >= mid) {
			pr[i] = min(pr[mid * 2 - i], maxr - i);
		}
		else pr[i] = 1;
		while (node[i + pr[i]] == node[i - pr[i]]) {
			pr[i]++;
		}
		if (pr[i] + i > maxr) {
			maxr = pr[i] + i;
			mid = i;
		}
		if (pr[i] - 1 >= extralen &&
			(i - pr[i] == 0 || i + pr[i] == nn 
				|| i - pr[i] == 1 || i + pr[i] == nn + 1) ) {
			extralen = pr[i] - 1; 
			weizhi = i;
		}
	}
}
signed main() {
	std::ios::sync_with_stdio(false);
	int T;
	cin >> T;
	while (T--){
		cin >> yuan + 1;
		int shouweilen = 0,len = strlen(yuan + 1);
		for (int i = 1, j = len; i <= len; i++, j--) {
			if (yuan[i] == yuan[j]) {
				shouweilen = i;
			}
			else break;
		}
		for (int i = 1; i <= shouweilen; i++) {
			cout << yuan[i];
		}
		if (shouweilen == len) {
			cout << "\n"; continue;
		}
		dr(shouweilen + 1, len - shouweilen);
		/*for (int i = 1; i <= nn; i++) { cout << "i = "<< i<<" :"<<node[i] << " " << pr[i]<<endl; }*/
		for (int i = weizhi - pr[weizhi] + 1; i < weizhi + pr[weizhi]; i++) {
			if (node[i] == '|')continue;
			else cout << node[i];
		}
		for (int i = len - shouweilen + 1; i <= len ; i++) {
			cout << yuan[i];
		}
		cout << "\n";
		for (int i = 0; i <= nn + 2; i++)
			pr[i] = 0, node[i] = '\0';
	}
	return 0;
}