0pts求条
查看原帖
0pts求条
891606
2023gdgz01楼主2024/12/3 13:36

Rt

#include <iostream>
#include <string>

using namespace std;

bool flag;
int n;
unsigned int mul = 131, Temp, _first, _second, Hash[2000005], power[2000005];
string s, ans, temp;

inline unsigned int get(int l, int r)
{
	return Hash[r] - Hash[l - 1] * power[r - l + 1];
}

inline unsigned int cal(int l, int r, int pos)
{
	return get(l, pos - 1) * power[r - pos] + get(pos + 1, r);
}

inline unsigned long long First(int pos)
{
	if (pos <= n / 2)
	{
		return cal(1, n / 2 + 1, pos);
	}
	return get(1, n >> 1);
}

inline unsigned long long Second(int pos)
{
	if (pos <= n / 2 + 1)
	{
		return get(n / 2 + 2, n);
	}
	if (pos < n)
	{
		return cal(n / 2 + 2, n, pos);
	}
	return get(n / 2 + 1, n - 1);
}

inline string sub(int pos)
{
	if (pos <= n / 2)
	{
		return s.substr(n / 2 + 2, n >> 1);
	}
	return s.substr(1, n >> 1);
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> s;
	s = ' ' + s;
	power[0] = 1;
	for (register int i = 1; i <= n; ++i)
	{
		power[i] = power[i - 1] * mul;
		Hash[i] = Hash[i - 1] * mul + s[i];
	}
	for (register int i = 1; i <= n; ++i)
	{
		_first = First(i);
		_second = Second(i);
		if (_first == _second)
		{
			if (flag && _first != Temp)
			{
				ans = "NOT UNIQUE";
				break;
			}
			ans = sub(i);
			Temp = _first;
			flag = true;
		}
	}
	if (!flag)
	{
		ans = "NOT POSSIBLE";
	}
	cout << ans;
	return 0;
}
2024/12/3 13:36
加载中...