66分求助
查看原帖
66分求助
461407
Withershine楼主2023/11/22 17:24

马拉车。

#include<bits/stdc++.h>
// #include<windows.h>
#define ll long long
#define fr(i , a , b) for(ll i = a ; i <= b ; ++i)
#define fo(i , a , b) for(ll i = a ; i >= b ; --i)
using namespace std;
ll n;
ll is[22000005];
char s[22000005] , a[22000005];
inline void change()
{
	ll cnt = 0;
	a[++cnt] = '#';
	a[++cnt] = '#';
	fr(i , 1 , n)
	{
		a[++cnt] = s[i];
		a[++cnt] = '#';
	}
	n = cnt;
}
ll ans , sum;
inline void manacher()
{
	ll maxn = 0 , mid = 0;
	fr(i , 2 , n)
	{
		if(i <= maxn)
		{
			is[i] = min(is[(mid << 1) - i] , mid - i + 1);
		}
		else
		{
			is[i] = 1;
		}
		while(a[i - is[i]] == a[i + is[i]])
		{
			is[i]++;
		}
		if(i + is[i] > maxn)
		{
			maxn = i + is[i] - 1;
			mid = i;
		}
		ans = max(ans , is[i]);
	}
}
signed main()
{
	scanf("%s" , s + 1);
	n = strlen(s + 1);
	change();
	manacher();
	printf("%lld\n" , ans - 1);
	// system("pause");
	return 0;
}
2023/11/22 17:24
加载中...