求助manacher算法
  • 板块学术版
  • 楼主wang1234567
  • 当前回复1
  • 已保存回复1
  • 发布时间2021/6/26 13:47
  • 上次更新2023/11/4 21:28:01
查看原帖
求助manacher算法
305900
wang1234567楼主2021/6/26 13:47

20分,为什么啊各位大佬?

#include<bits/stdc++.h>
using namespace std;
char s[30000000];
int l=2,p[30000000],maxn=0;
void _int()
{
	s[0]='&';s[1]='#';
	char x=getchar();
	while(x>='a'&&x<='x')
	{
	    s[l++]=x;
	    s[l++]='#';
		x=getchar();
	}
	s[l]='^';
	return;
}
int main()
{
	_int();
	int mid,r=1;
	for(int i=1;i<l;i++)
	{
		if(i<r)
			p[i]=min(p[mid-(i-mid)],r-i);
		else
			p[i]=1;
		while(s[i+p[i]]==s[i-p[i]])
			p[i]++;
		if(r<i+p[i])
		{
			mid=i;
			r=i+p[i];
		}
		maxn=max(maxn,p[i]-1);
	}
	cout<<maxn<<endl;
	return 0;
}
2021/6/26 13:47
加载中...