#C241119A. 字符串

标签（Label）

• 哈希

网址（Website）

题目详情 - 字符串 - Super

题解 - 字符串 - Super

题目（Problem）

输入数据 1

7  
ABXCABC

输出数据 1

ABC

输入数据 2

6  
ABCDEF

输出数据 2

NOT POSSIBLE

输入数据 3

9  
ABABABABA

输出数据 3

NOT UNIQUE

题解（Solution）

$\qquad$双哈希又被卡了。。。我写的是 Hash 做法，直接提取出字符串计算就好了。

$\qquad$容易理解错的地方是只有 $S$ 不唯一才输出 NOT UNIQUE ，如果有多种方案都能获得 $S$ 并不需要输出。

出题者题解

代码（Code）

100分

#include<bits/stdc++.h> 
#include<vector>
#include<queue>
#include<stack>
#include<set>
#include<map>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define Rof(i,l,r) for(int i=l;i>=r;i--)
using namespace std;
#define P pair<int,int> 
#define int long long
#define x first
#define y second
const int inf = 0x3f3f3f3f3f3f3f3f;
const int N = 2012345;
bool ST;

int n,mid,ans;
string s;

/*
我双哈希又被卡了 
记录模数：
m1 = 998244353, b1 = 131
m2 = 1e9+9, b2 = 997;
*/
namespace H{
	const int m1 = 998244353, b1 = 131;
	const int m2 = 1e9+97, b2 = 997;
	int f1[N], p1[N];
	int f2[N], p2[N];
	void init(){
		p1[0]=1;For(i,1,n+5) p1[i] = p1[i-1]*b1%m1;
		p2[0]=1;For(i,1,n+5) p2[i] = p2[i-1]*b2%m2;
		For(i,1,n) f1[i] = (f1[i-1]*b1 + s[i]-'A'+1)%m1;
		For(i,1,n) f2[i] = (f2[i-1]*b2 + s[i]-'A'+1)%m2;
	}
	inline int calc1(int l,int r){return l<=r ? (f1[r] - p1[r-l+1]*f1[l-1]%m1 + m1)%m1 : 0;}
	inline int calc2(int l,int r){return l<=r ? (f2[r] - p2[r-l+1]*f2[l-1]%m2 + m2)%m2 : 0;}
	inline P calc(int l,int r){
		int t1 = (f1[r] - p1[r-l+1]*f1[l-1]%m1 + m1)%m1;
		int t2 = (f2[r] - p2[r-l+1]*f2[l-1]%m2 + m2)%m2;
		return {t1,t2};
	}
	inline P delstr(int l,int r,int L=1,int R=n){
		int t1 = (calc1(L,l-1)*p1[R-r]%m1 + calc1(r+1,R))%m1;
		int t2 = (calc2(L,l-1)*p2[R-r]%m2 + calc2(r+1,R))%m2;
		return {t1,t2};
	}
}

void Solve(){
	cin>>n>>s, mid=n/2+1, s=" "+s;
	if(n%2==0) return cout<<"NOT POSSIBLE\n",void();
	H::init();
	auto left = H::calc(1,mid-1);
	auto right = H::calc(mid+1,n);
	if(left==right) return cout<<s.substr(1,mid-1)<<'\n',void();
	For(i,1,mid-1){
		auto tmp = H::delstr(i,i,1,mid);
		if(tmp == right) ans = 2;
	}
	For(i,mid+1,n){
		auto tmp = H::delstr(i,i,mid,n);
		if(tmp == left){
			if(ans==2) return cout<<"NOT UNIQUE\n" ,void();
			ans = 1;
		}
	}
	switch(ans){
		case 0:{cout<<"NOT POSSIBLE\n";break;}
		case 1:{cout<<s.substr(1,mid-1)<<'\n';break;}
		case 2:{cout<<s.substr(mid+1,n)<<'\n';break;}
	}
}

bool ED;
signed main(){
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cerr<<abs(&ST-&ED)/1024./1024.<<"MB\n";
	freopen("string.in","r",stdin);
	freopen("string.out","w",stdout);
	int Tt=1;double Tim=clock();
	while(Tt--) Solve();
	return cerr<<"TIME:"<<(clock()-Tim)/CLOCKS_PER_SEC,0;
}