friends/三个好朋友

思路

代码

#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef unsigned long long ull;
const int N=2e6 + 10;
char s[N];
ull _hash[N];
ull base=23333;
ull base_s[N];
char ans[N];
ull pre;

int n;
void init(){
    base_s[0]=1;
    for(int i=1;i<=n;i++){
        _hash[i]=_hash[i-1]*base+s[i];
        base_s[i]=base_s[i-1]*base;
    }
}
ull get(int l,int r){
    return _hash[r]-_hash[l-1]*base_s[r-l+1];
}
bool judge(int pos){
    int mid=(n>>1)+1;
    ull l,r;
    if(pos<mid){
        l=get(1,pos-1)*base_s[mid-pos]+get(pos+1,mid);
        r=get(mid+1,n);
    }
    if(pos==mid){
        l=get(1,mid-1);
        r=get(mid+1,n);
    }
    if(pos>mid){
        l=get(1,mid-1);
        r=get(mid,pos-1)*base_s[n-pos]+get(pos+1,n);
    }
    if(l==r){
        if(pre==l)return false;//如果出现过，就不用再记录了
        pre=l;
        int sz=0;
        if(pos<=mid){
            for(int i=1;i<=mid;i++){
                if(i==pos)continue;
                ans[sz++]=s[i];
            }
        }
        else {
            for(int i=1;i<mid;i++){
                ans[sz++]=s[i];
            }
        }
        return true;
    }
    return false;
}
int main(){
    scanf("%d%s",&n,s+1);
    
    if(n%2==0){
        puts("NOT POSSIBLE");
        return 0;
    }
    init();
    int cnt=0;//cnt几下有几种方案
    for(int i=1;i<=n;i++){
        if(judge(i))//枚举一下哪一个字符是插入的u
            cnt++;
    }
    if(cnt==0)puts("NOT POSSIBLE");
    else if(cnt==1)puts(ans);
    else puts("NOT UNIQUE");
    return 0;
}