看了一下最优解用的是这样的代码:

void manacher_fast()
{
  	for(int i=1;str[i];i++)
	{
		int l=i,r=i;
		while(str[i]==str[r+1]) r++;
		i=r;
		while(str[l-1]==str[r+1]) --l,++r;
		ans=max(ans,r-l+1);
	}
}

但这么做好像不是线性的,自己写了一个数据生成器把这个做法卡TLE了

#include <iostream>

using namespace std;

int main()
{
	freopen("test.in","w",stdout);
	for(int i=0;i<=500000;i++) printf("ab");
	return 0;
}
 

是不是因为数据太弱了导致这种做法可以跑的飞快