关于Manacher
查看原帖
关于Manacher
109220
Farkas_W楼主2020/12/11 18:31

为什么用string类型会全RE,用char类型就过了

//char 类型
#include<iostream>
#include<cstdio>
#include<cmath>
#include<string>
#include<cstring>
#include<algorithm>
#define int long long
#define re register int
#define il inline
#define pc(x) putchar(x)
#define max(x,y) x>y?x:y
#define min(x,y) x<y?x:y
using namespace std;
il void print(int x)
{
  if(x<0)pc('-'),x=-x;
  if(x/10)print(x/10);
  pc(x%10+'0');
}
const int N=22000500;
int ans,p[N],f,len,l,Max,t;
char s1[N],s2[N];
signed main()
{
	cin>>s1;len=strlen(s1);s2[t++]='#';
	for(re i=1;i<=len;i++)s2[t++]='#',s2[t++]=s1[i-1];
	s2[t]='#';len=len*2+1;
	for(re i=1;i<=len;i++)
	{
		if(i<f)p[i]=min(f-i,p[l-(i-l)]);
		while(s2[i+p[i]+1]==s2[i-p[i]-1]&&i+p[i]+1<=len)p[i]++;
		if(p[i]+i>f)f=p[i]+i,l=i;
		Max=max(p[i],Max);
	}print(Max);
	return 0;
}
//string 类型
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#define int long long
#define re register int
#define il inline
#define pc(x) putchar(x)
#define max(x,y) x>y?x:y
#define min(x,y) x<y?x:y
using namespace std;
il void print(int x)
{
  if(x<0)pc('-'),x=-x;
  if(x/10)print(x/10);
  pc(x%10+'0');
}
const int N=2e7+5e6;
int ans,p[N],f,len,l,Max,t;
string s1,s2;
signed main()
{
	cin>>s1;len=s1.size();s2[t++]='#';
	for(re i=1;i<=len;i++)s2[t++]='#',s2[t++]=s1[i-1];
	s2[t]='#';len=len*2+1;
	for(re i=1;i<=len;i++)
	{
		if(i<f)p[i]=min(f-i,p[l-(i-l)]);
		while(s2[i+p[i]+1]==s2[i-p[i]-1]&&i+p[i]+1<=len)p[i]++;
		if(p[i]+i>f)f=p[i]+i,l=i;
		Max=max(p[i],Max);
	}print(Max);
	return 0;
}
2020/12/11 18:31
加载中...