#61 TLE求助
查看原帖
#61 TLE求助
1432013
DashZhanghanxu楼主2025/6/23 21:55
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define int long long
#define O2 ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
const int N=1e6*2+10;
int P=131;
int n;
string s;
int start=-1,endd=-1;
int Hash[N];
int p[N];
int get1(int l,int r){
	return Hash[r]-Hash[l-1]*p[r-l+1];//abc
}
int get2(int l,int r,int b){
	return get1(l,b-1)*p[r-b]+get1(b+1,r); //abcabxc
}
signed main(){
    O2;
    cin>>n>>s;
    p[0]=1;
    for(int i=1;i<=n;i++){
    	p[i]=p[i-1]*P;
	}
	if(n%2==0){
		cout<<"NOT POSSIBLE";
		return 0;
	}
	for(int i=0;i<n;i++){
		Hash[i+1]=Hash[i]*P+s[i];
	}
	int mid=(n+1)/2;
	int flag=0;
	int k1=get1(mid+1,n),k2=get1(1,mid-1);
	//abcabcx
	
	if(get1(2,mid)==get1(1+mid,n)){
		//ans=s.substr(1,mid-1);
		start=1,endd=mid-1;
		flag=1;
	}
	if(get1(1,mid-1)==get1(mid,n-1)){
		if(flag==1&&(s.substr(start,endd)!=s.substr(0,mid-1))){
			cout<<"NOT UNIQUE";
			return 0; 
		}
		//ans=s.substr(0,mid-1);
		start=0,endd=mid-1;
		flag=1;
	}
	//string fw=s.substr(mid,n-mid),fw2=s.substr(0,mid-1);
    for(int i=2;i<n;i++){
    	if(i<mid){
    		if(get2(0,mid,i)==k1){
    			if(flag==0){
				flag=1;
				//ans=fw;
				start=mid,endd=n-mid;
    			}else if(s.substr(start,endd)!=s.substr(mid,n-mid)){
    				cout<<"NOT UNIQUE";
    				return 0;
				}
			}
		}else if(i>mid){
			if(get2(mid,n,i)==k2){
    			if(flag==0){
				flag=1;
				//ans=fw2;
				start=0,endd=mid-1;
			}else if(s.substr(start,endd)!=s.substr(0,mid-1)){
    				cout<<"NOT UNIQUE";
    				return 0;
				}
			}
		}else{
			if(get1(1,i-1)==get1(i+1,n)){
				//ans=s.substr(0,i-1);
				start=0,endd=i-1;
				flag=1;
			}
		}
	}
	if(flag){
		cout<<s.substr(start,endd);
	}else{
		cout<<"NOT POSSIBLE";
	}
    return 0;
}

2025/6/23 21:55
加载中...