CF-1326D

發表於 更新於 Disqus：

You are given a string $s$, consisting of lowercase English letters. Find the longest string, $t$, which satisfies the following conditions:

  • The length of $t$ does not exceed the length of $s$.
  • $t$ is a palindrome.
  • There exists two strings $a$ and $b$ (possibly empty), such that $t=a+b$ ( “$+$” represents concatenation), and $a$ is prefix of $s$ while $b$ is suffix of $s$.

Easy Version: $|s|\leq 5000$

Hard Version: $|s|\leq 10^6$

把左右一樣的砍掉，他們肯定回文
中間的看要取左或取右，並且也要是回文
學完manacher’s algorithm後把他砸在這題><
複雜度$\mathcal{O}(n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <bits/stdc++.h>
using namespace std;

void solve() {
	string s;
	cin >> s;
	int n = s.size();
	int border = 0;
	while(border<n-border-1 && s[border]==s[n-border-1]) border++;
	string a = "#";
	for(int i = border; i < n-border; i++) {
		a.push_back(s[i]);
		a.push_back('#');
	}
	int l = 0, r = -1, x, y=-1;
	vector<int> arr(a.size());
	for(int i = 0; i < a.size(); i++) {
		arr[i]= i<=r?min(arr[2*l-i], r-i):0;
		while(~(i-arr[i]) && i+arr[i]<a.size() && a[i+arr[i]]==a[i-arr[i]]) arr[i]++;
		if(i+arr[i]-1 > r) r=i+arr[i]-1, l=i;
		if(arr[i]-1==i) x=i;
		if(arr[i]+i==a.size() && y<0) y=i;
	}
	if(arr[x]>arr[y]) {
		cout << s.substr(0, border) << s.substr(border, arr[x]-1) << s.substr(n-border, border);
	}
	else {
		cout << s.substr(0, border) << s.substr(n-border-arr[y]+1, arr[y]-1) << s.substr(n-border, border);
	}
	cout << '\n';
}
 
signed main() {
	ios::sync_with_stdio(0); cin.tie(NULL);
 
	int t;
	cin >> t;
	while(t--) solve();
 
	return 0;
}