题目

小j这学期有门课叫密码学，他自己想了一种加密方式。 他手上有一个字符串 S，先将 S 复制一次得到字符串 T，然后在 T 中插入一个字符，得到字符串 U。 但小f说你这个加密一点都不牛逼，他一只手就能给你太阳过去。

现在小j给出字符串 U，要小f构造出字符串 S。由于小f的手有要事要干，所以这个任务就交给你来完成了。 所有字符串只包含大写英文字母。

输入：第一行一个整数 N，表示字符串 U 的长度；第二行一个长度为 N 的字符串，表示 U。
输出：一行一个字符串，表示 S。若无法构造输出 NOT POSSIBLE；若 S 不唯一输出 NOT UNIQUE。
数据范围：46% 的数据 N ≤ 2000；100% 的数据 N ≤ 5×105。

样例：
输入 7 / ABXCABC → 输出 ABC

思路

U 的长度 N 必须是奇数，否则无论在哪插入一个字符都凑不出两段相等的 S，直接 NOT POSSIBLE。 设 L = (N-1)/2。

暴力做法（p96.cpp）：枚举每个位置 c（0 到 N-1）作为插入点，删掉 U[c] 后检查前后两半是否相同，记录合法 S，有冲突输出 NOT UNIQUE。时间复杂度 O(N²)。

优化做法（p96+.cpp）：先扫一遍，找第一个让 U[c] ≠ U[c+L+1] 的位置 p。 若 p == -1，左右本来全匹配，插入点只可能是中间位置 L；否则，差异只可能由位置 p 或 p+L+1 引起，候选至多 2 个。 check() 直接用下标跳过插入位置逐字符比较，总复杂度 O(N)，通过 92%。

C++ · p96.cpp  ·  暴力 O(N²) 
#include<bits/stdc++.h>
using namespace std;

int main(){
    int N;
    string S;
    cin>>N>>S;
    if(N%2==0){
        cout<<"NOT POSSIBLE"<<endl;
        return 0;
    }
    int L = (N-1)/2;
    string result;
    bool only=true;
    for(int c=0;c<N;c++){
        string T=S.substr(0, c)+S.substr(c+1);
        if(T.substr(0, L) == T.substr(L)) {
            if(result.empty()){
                result=T.substr(0,L);;
            }else if(T.substr(0,L)!=result){
                only=false;
                cout<<"NOT UNIQUE"<<endl;
                return 0;
            }
        }
    }
    if(result.empty()) cout<<"NOT POSSIBLE"<<endl;
    else cout<<result<<endl;
    return 0;
}
C++ · p96+.cpp  ·  优化 O(N)  ·  92% 
#include<bits/stdc++.h>
using namespace std;

// 假设插入的字符在位置c，验证去掉它之后两半是否相同
bool check(string& U, int c, int L){
    for(int c1=0;c1<L;c1++){
        char ti  = (c1 < c)   ? U[c1]   : U[c1+1];
        char tiL = (c1+L < c) ? U[c1+L] : U[c1+L+1];
        if(ti != tiL) return false;
    }
    return true;
}

int main(){
    int N;
    string S;
    cin>>N>>S;
    if(N%2==0){
        cout<<"NOT POSSIBLE"<<endl;
        return 0;
    }
    int L = (N-1)/2;
    string result;
    bool only=true;
    int p=-1;
    for(int c=0;c<L;c++){
        if(S[c]!=S[c+L+1]){
            p=c;
            break;
        }
    }
    vector<int> candidates;
    if(p==-1){
        candidates = {L};
    }else{
        candidates = {p, p+L+1};
    }
    for(int c : candidates){
        if(check(S,c,L)){
            string current = (S.substr(0,c)+S.substr(c+1)).substr(0,L);
            if(result.empty()){
                result=current;
            }else if(result!=current){
                only=false;
            }
        }
    }
    if(result.empty()){
        cout<<"NOT POSSIBLE"<<endl;
    }else if(!only){
        cout<<"NOT UNIQUE"<<endl;
    }else{
        cout<<result<<endl;
    }
    return 0;
}

复杂度分析

  • p96.cpp（暴力）：时间 O(N²)，空间 O(N)。
  • p96+.cpp（优化）：时间 O(N)，空间 O(N)，通过 92%。
今日感受

暴力版思路清晰，枚举插入点再比较两半。优化版的核心是：两半扫到不一样，插入点就被锁死，候选从 N 个降到 2 个。
这题让我学到了 substr 的用法——substr(pos, len) 截取从 pos 开始长度为 len 的子串，substr(pos) 截取到末尾。也补充了以前忘记的 .empty() 判断，比 result == "" 更正规。

← 返回菜鸟的coding