蒟蒻76分求助
查看原帖
蒟蒻76分求助
396547
MilkaThePigeon楼主2022/7/5 11:25
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define MAXN 11000005
using namespace std;
char s[MAXN],ss[MAXN];
int pos,maxp,n,maxr;
int p[MAXN];
void search(int a)
{
	while(ss[a+p[a]+1]==ss[a-p[a]+1]) p[a]++;
	return;
}
void init(){
    ss[0]='@';
	ss[1]='#';
    for(int i=0;i<n;i++)
    {
        ss[i*2+2]=s[i];
        ss[i*2+3]='#';
    }
    n=n*2+2;
}
int main()
{
	scanf("%s",s);
	n=strlen(s);
	init();
	for(int i=0;i<=n;i++)
	{
		if(i<maxr) p[i]=min(p[pos*2-i],maxr-i);
		else p[i]=1;
		search(i);
		if(i+p[i]>maxr) maxr=i+p[i],pos=i;
		maxp=max(maxp,p[i]);
	}
	printf("%d",maxp-1);
	return 0;
}

卡#3、#7、#11

2022/7/5 11:25
加载中...