mxqz manacher 板子
查看原帖
mxqz manacher 板子
324666
diqiuyi奶龙楼主2023/4/15 10:23

rt,TLE

#include <bits/stdc++.h>
using namespace std;
int n,len,hw[2000050],mid,mr,ans,pos;
string s,news;
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	while(cin>>s){
		len=s.size();
		news="##";
		for(int i=0;i<len;i++)
			news+=s[i],news+='#';
		n=news.size();
		for(int i=1;i<n;i++){
			if(i<mr) hw[i]=min(hw[(mid<<1)-i],mr-i);
			else hw[i]=1;
			while(news[i+hw[i]]==news[i-hw[i]]) hw[i]++;
			if(i+hw[i]>mr) mr=i+hw[i],mid=i;
			if(i+hw[i]==n){
				pos=i-hw[i];
				break;
			}
		}
		cout<<s;
		for(int i=(pos>>1)-1;i>=0;i--)
			cout<<s[i];
		cout<<'\n';
	}
	return 0;
}


2023/4/15 10:23
加载中...