欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

friends/三个好朋友

程序员文章站 2022-06-13 11:36:46
...

思路

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;
}
相关标签: hash