Friends

一本通·提高篇 · 代码 · cpp · 难度 5/5 · 共 1990 字
双哈希枚举删除位还原S并判唯一
一本通
练习
正文

// 原题：https://oj.yecheng.tv/p/T1459
// 题意：给长度 N 与串 U（由 S 复制成 SS 后插入一个字符得到），求原串 S；不唯一输出 NOT UNIQUE，不存在输出 NOT POSSIBLE。
// 思路：N 为偶数直接无解；否则 m=N/2，用双哈希 O(1) 比较"删掉第 i 位后前后两半是否相等"，收集不同的候选 S 判重。
// 复杂度：O(N) 时间 / O(N) 空间
// 易错点：删除位在前半段和后半段时，左右两半的拼接区间不同，下标要分开推导；哈希要双份防碰撞导致误判唯一。
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
const ull B1=911382323ull;
const ull B2=972663749ull;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N;
    if(!(cin>>N)) return 0;
    string u;
    if(!(cin>>u)) return 0;
    if(N%2==0){
        cout<<"NOT POSSIBLE\n";
        return 0;
    }
    int m=N/2;
    int n=N;
    vector<ull> h1(n+1,0),h2(n+1,0),p1(n+1,1),p2(n+1,1);
    for(int i=0;i<n;i++){
        ull v=(ull)(u[i]-'A'+1);
        h1[i+1]=h1[i]*B1+v;
        h2[i+1]=h2[i]*B2+v;
        p1[i+1]=p1[i]*B1;
        p2[i+1]=p2[i]*B2;
    }
    auto g1=[&](int l,int r)->ull{
        if(l>r) return 0ull;
        return h1[r+1]-h1[l]*p1[r-l+1];
    };
    auto g2=[&](int l,int r)->ull{
        if(l>r) return 0ull;
        return h2[r+1]-h2[l]*p2[r-l+1];
    };
    bool found=false;
    bool uniq=true;
    ull c1=0,c2=0;
    string ans;
    for(int i=0;i<n;i++){
        ull L1,L2,R1,R2;
        if(i<m){
            L1=g1(0,i-1)*p1[m-i]+g1(i+1,m);
            L2=g2(0,i-1)*p2[m-i]+g2(i+1,m);
            R1=g1(m+1,n-1);
            R2=g2(m+1,n-1);
        }else{
            L1=g1(0,m-1);
            L2=g2(0,m-1);
            R1=g1(m,i-1)*p1[n-1-i]+g1(i+1,n-1);
            R2=g2(m,i-1)*p2[n-1-i]+g2(i+1,n-1);
        }
        if(L1!=R1||L2!=R2) continue;
        if(!found){
            found=true;
            c1=L1;
            c2=L2;
            if(i<m) ans=u.substr(0,i)+u.substr(i+1,m-i);
            else ans=u.substr(0,m);
        }else if(L1!=c1||L2!=c2){
            uniq=false;
            break;
        }
    }
    if(!found) cout<<"NOT POSSIBLE\n";
    else if(!uniq) cout<<"NOT UNIQUE\n";
    else cout<<ans<<'\n';
    return 0;
}
Friends

正文

一本通·提高篇的其它内容
