#3 TLE求助
查看原帖
#3 TLE求助
487383
imnoob楼主2024/7/18 20:11
#include <bits/stdc++.h>
using namespace std;
string s;
char c[200010];
int n, ans = 0, d[200010], z[200010], y[200010];
int main()
{
	cin >> s;
	c[0] = '-';
	c[1] = '#';
	for(int i = 1; i <=	 s.length(); ++i)
	{
		c[i * 2] = s[i - 1];
		c[i * 2 + 1] = '#';
	}
	n = s.length() * 2 + 1;
	c[n + 1] = '/';
	int p = 0;
	for(int i = 1; i <= n; ++i)
	{
		if(i <= p + d[p])
		{
			d[i] = min(d[p * 2 - i], p + d[p] - i);
		}
		while(c[i + d[i] + 1] == c[i - d[i] - 1])
		{
			++d[i];
		}
		y[i + d[i]] = max(y[i + d[i]], d[i]);
		z[i - d[i]] = max(z[i - d[i]], d[i]);
	}
	for(int i = 3; i <= n; i += 2)
	{
		z[i] = max(z[i], z[i - 2] - 2);
	}
	for(int i = n; i >= 3; i -= 2)
	{
		y[i] = max(y[i], y[i + 2] - 2);
	}
	for(int i = 3; i <= n; i += 2)
	{
		if(z[i] && y[i])
		{
			ans = max(ans, z[i] + y[i]);
		}
	}
	cout << ans;
	return 0;
} 
2024/7/18 20:11
加载中...