BOI 2014 day 1

friends.cpp

#include <bits/stdc++.h>

using namespace std;

#define llint long long

const int MAXN = 2000100;
const llint A = 29;
const llint B = 31;
const llint MOD1 = 1000000007;
const llint MOD2 = 1000000009;

int n;
string str;

llint hashes1[MAXN], hashes2[MAXN];
llint pows1[MAXN], pows2[MAXN];

void init()
{
	int i;
	
	hashes1[n] = hashes2[n] = 0;
	for (i = n - 1; i >= 0; --i)
	{
		hashes1[i] = (A * hashes1[i + 1] + str[i] - 'A') % MOD1;
		hashes2[i] = (B * hashes2[i + 1] + str[i] - 'A') % MOD2;
	}
	
	pows1[0] = pows2[0] = 1;
	for (i = 1; i <= n; ++i)
	{
		pows1[i] = A * pows1[i - 1] % MOD1;
		pows2[i] = B * pows2[i - 1] % MOD2;
	}
}

pair<llint, llint> substr(int i, int k)
{
	return make_pair((hashes1[i] + MOD1 - hashes1[i + k] * pows1[k] % MOD1) % MOD1, (hashes2[i] + MOD2 - hashes2[i + k] * pows2[k] % MOD2) % MOD2);
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	int i;
	string sol = "";
	pair<int, int> hsh;
	
	cin>>n>>str;
	
	if (n % 2 == 0)
	{
		cout<<"NOT POSSIBLE"<<endl;
		return 0;
	}
	
	string a = str.substr(n / 2 + 1), b = str.substr(0, n / 2);
	
	if (n < 300000)
	{
		if (str.substr(0, n / 2) == str.substr(n / 2 + 1, n / 2))
		{
			sol = a;
		}
		
		for (i = 0; i < n / 2; ++i) if (str.substr(0, i) == str.substr(n / 2 + 1, i) && str.substr(i + 1, n / 2 - i) == str.substr(n / 2 + 1 + i, n / 2 - i))
		{
	//		cout<<i<<endl;
			if (sol.size() && sol != a)
			{
				cout<<"NOT UNIQUE"<<endl;
				return 0;
			}
			sol = a;
		}
		
		for (i = n / 2 + 1; i < n; ++i) if (str.substr(0, i - n / 2) == str.substr(n / 2, i - n / 2) && str.substr(i - n / 2, n - i - 1) == str.substr(i + 1, n - i - 1))
		{
	//		cout<<i<<endl;
			if (sol.size() && sol != b)
			{
				cout<<"NOT UNIQUE"<<endl;
				return 0;
			}
			sol = b;
		}
		
	//	cout<<substr(0, n / 2 - 1)<<' '<<substr(n / 2 + 1, n / 2 - 1)<<endl;
	//	cout<<sol<<endl;
		
		goto end;
	}
	
	init();
	
	if (substr(0, n / 2) == substr(n / 2 + 1, n / 2))
	{
		sol = a;
	}
	
	for (i = 0; i < n / 2; ++i) if (substr(0, i) == substr(n / 2 + 1, i) && substr(i + 1, n / 2 - i) == substr(n / 2 + 1 + i, n / 2 - i))
	{
//		cout<<i<<endl;
		if (sol.size() && sol != a)
		{
			cout<<"NOT UNIQUE"<<endl;
			return 0;
		}
		sol = a;
		break;
	}
	
	for (i = n / 2 + 1; i < n; ++i) if (substr(0, i - n / 2) == substr(n / 2, i - n / 2) && substr(i - n / 2, n - i - 1) == substr(i + 1, n - i - 1))
	{
//		cout<<i<<endl;
		if (sol.size() && sol != b)
		{
			cout<<"NOT UNIQUE"<<endl;
			return 0;
		}
		sol = b;
		break;
	}
	
//	cout<<substr(0, n / 2 - 1)<<' '<<substr(n / 2 + 1, n / 2 - 1)<<endl;
//	cout<<sol<<endl;
	
	end:
	
	if (sol.empty())
		cout<<"NOT POSSIBLE"<<endl;
	else cout<<sol<<endl;
}