题解：P8131 [ICPC 2020 WF] Gene Folding

思路

这道题我们可以先思考一下暴力一点的做法，再思考如何让优化。那怎么暴力呢，可以递归循环 Manacher 算法，每次删除最长回文串，直到 $maxlen - 1 = 1$ 退出循环，再看一下时限，$5$ 秒好像还挺充裕的，但实际呢，还是 TLE。

所以我们就要想一下怎样避免递归。这时候我们就可以定义一个 $l$ 和 $r$，先用 Manacher 算出所有的 $p_i$，在从左到右遍历一遍 $res$，如果 $res_i =$ #，即此回文串为偶回文串，并且 $i - p_i \le l$，即有新的偶回文串可以删除，使 $l = i$，因为只删一半。$r$ 同理，只不过是从右往左遍历，使 $i + p_i \ge r$ 即可。

最后的答案便是 $(r - l) / 2$。

Code

#include <bits/stdc++.h>
using namespace std;
const int N=4e7+5;

string ss;
int p[N*2+5];

int read(){
	int x=0,f=1;char c=getchar();
	while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
	while (c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}
	return x*f;
}

int manacher(string s){
	string res="$#";
	for (int i=0;i<s.size();i++){
		res+=s[i];
		res+="#";
	}
	int maxright=0,pos=0;
	int l=0,r=res.size()-1;
	for (int i=1;i<res.size();i++){
		p[i]=maxright>i?min(p[pos*2-i],maxright-i):1;
		while (res[i+p[i]]==res[i-p[i]]){
			p[i]++;
		}
		if (maxright<i+p[i]){
			maxright=i+p[i];
			pos=i;
		}
	}
	for (int i=1;i<res.size();i++)
		if (i-p[i]<=l&&res[i]=='#')
			l=i;
	for (int i=res.size()-1;i>l;i--)
		if (i+p[i]>=r&&res[i]=='#')
			r=i;
//	cout <<l<<" "<<r<<endl; 
	return (r-l)/2;
}

int main(){
	cin >>ss;
	cout <<manacher(ss)<<endl;
	return 0;
}