萌新刚学 OI,求助有关 Manacher 算法的一些问题
  • 板块灌水区
  • 楼主Brainless_zxc
  • 当前回复8
  • 已保存回复8
  • 发布时间2024/4/12 08:57
  • 上次更新2024/4/12 16:24:08
查看原帖
萌新刚学 OI,求助有关 Manacher 算法的一些问题
661274
Brainless_zxc楼主2024/4/12 08:57

我的代码:

#include<bits/stdc++.h>
using namespace std;
char a[11000005],s[22000005];
long long P[22000005],ans=1,n,k;
inline void Manacher(){
	int R,c=0;
	for(int i=1;i<n;i++){
		if(i>=R){
			P[i]=1;
		}
		else{
			P[i]=min(P[c]+c-i,P[2*c-i]);
		}
		while(s[i+P[i]]==s[i-P[i]]){
			P[i]++;
		}
		if(i+P[i]>=R){
			R=i+P[i];
			c=i;
		}
	}
}
int main(){
	scanf("%s",a);
	n=strlen(a);
	s[k++]='S';
	s[k++]='$';
	for(int i=0;i<n;i++){
		s[k++]=a[i];
		s[k++]='$';
	}
	s[k++]='B';
	n=k;
	Manacher();
	for(int i=0;i<n;i++){
		ans=max(ans,P[i]);
	}
	cout<<ans-1<<endl;
}

这份代码会 #1 WA,剩余点全部 RE。然后使用校内OJ的在线编译功能(Hydro 上的)调试,发现会有 RE 和 警告。附图:

然后把第 4 行 long long 改成 int ,没有RE了,只有警告。

然后经过修改发现 R 需要赋初值。加上初始值就AC了。而且警告也不见了。

于是有了以下几个问题:

  1. 为什么最开始的代码会WA + RE ?

  2. 为什么会有 'R' may be used uninitialized [-Wmaybe-uninitialized] 这样的警告?

  3. 这份代码空间并不大,为什么在线编译会 RE ?

  4. 经过测试,R 不赋初值会 WA + RE,但是 c 不赋初值不影响结果。而且R赋了初值后为什么警告也消失了?

  5. 这个警告什么意思。

2024/4/12 08:57
加载中...