社区讨论

为什么会t四个点

P3805【模板】Manacher参与者 1已保存回复 0

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
0 条
当前快照
1 份
快照标识符
@lo35l42b
此快照首次捕获于
2023/10/24 01:10
2 年前
此快照最后确认于
2023/10/24 01:10
2 年前
查看原帖
rt
CPP
// Problem: P3805 【模板】manacher 算法
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P3805
// Memory Limit: 512 MB
// Time Limit: 500000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
char dt[22000002];
int p[22000002];
int cnt;
inline void get(){
	char c=getchar();
	dt[0]='~';
	dt[1]='*';
	cnt=1;
	while(c<'a'||c>'z') c=getchar();
	while(c>='a'&&c<='z') dt[++cnt]=c,dt[++cnt]='*',c=getchar();
}
int main(){
	get();
	// cout<<dt;
	int ans=0;
	for(int i=1;i<cnt;++i){
		int r=0,mid=0;
		if(i<r+mid){
			p[i]=min(p[2*mid-i],r-i);
		}
		else p[i]=1;
		while(dt[i-p[i]]==dt[i+p[i]]){
			p[i]++;
		} 
		if(i+p[i]>r){
			r=i+p[i];
			mid=i;
		}
		ans=max(ans,p[i]-1);
	}
	cout<<ans;
	return 0;
}

回复

0 条回复,欢迎继续交流。

正在加载回复...