哈希太难调，没成功直接放弃……

首先，暴力很好想，直接枚举哪一个是插入的，把它删掉，再以中间为断点隔开两个字符子串，判断是否相同即可。注意如果 $n$ 为偶数，那么就是没有插入，直接输出 NOT POSSIBLE。好心的测试数据给了 $\color{#b0d628} 88$ 分。

#include <bits/stdc++.h>
using namespace std;

int n,cnt;
string s,ans,out;
bool flag;

signed main()
{
	scanf("%d",&n);
	cin >> s;
	if(n % 2 == 0){printf("NOT POSSIBLE");return 0;}
	for(int x = 0;x <= n / 2;x++)//哪个是插入的
	{
		char c = s[x];
		s[x] = '.';
		flag = true;
		for(int i = 0,j = n / 2 + 1;i <= n / 2;i++,j++)
		{
			if(s[i] == '.') i++;//跳过
			if(s[i] != s[j])
			{
				flag = false;//不可能
				break;
			}
			ans += s[i];
		}
		if(flag && out != ans){cnt++;out = ans;}
		if(cnt > 1){printf("NOT UNIQUE");return 0;}//不止一个
		ans = "";
		s[x] = c;
	}
	
	for(int x = n / 2;x < n;x++)//与上面一样
	{
		char c = s[x];
		s[x] = '.';
		flag = true;
		for(int i = 0,j = n / 2;i < n / 2;i++,j++)
		{
			if(s[j] == '.') j++;
			if(s[i] != s[j])
			{
				flag = false;
				break;
			}
			ans += s[i];
		}
		if(flag && out != ans){cnt++;out = ans;}
		if(cnt > 1){printf("NOT UNIQUE");return 0;}
		ans = "";
		s[x] = c;
	}
	if(cnt) cout << out;
	else printf("NOT POSSIBLE");
	return 0;
}
/*
11
ababcabaabc
aba??
*/

那么考虑优化，枚举哪个是插入的耗时过多，可以考虑直接断开两段，遇到不一样的就不管，最后看看有多少相同的即可。

#include <bits/stdc++.h>
using namespace std;

int n,cnt;
string s,o,t,ans;

signed main()
{
	scanf("%d",&n);
	cin >> s;
	if(n % 2 == 0){printf("NOT POSSIBLE");return 0;}
	o = s.substr(0,n / 2);//直接断
	t = s.substr(n - n / 2,n / 2);
	int i,j;
	
	for(i = 0,j = n / 2;i < n / 2 && j < n;j++) if(o[i] == s[j]) i++;//一样的个数
	if(i == n / 2){cnt++;ans = o;}//有答案了
	
	for(i = 0,j = 0;i < n / 2 && j < n - n / 2;j++) if(t[i] == s[j]) i++;//同上
	if(i == n / 2)
	{
		cnt++;
		if(cnt > 1 && ans != t){printf("NOT UNIQUE");return 0;}//答案不唯一
		ans = t;
	}
	
	if(!cnt) printf("NOT POSSIBLE");
	else cout << ans;
	return 0;
}

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
#include <map>
#define ll  long long
#define out(a) printf("%d ",a)
#define writeln printf("")
const int N=2e6+50;
const int MOD=1e9+7;
const int base=233;
using namespace std;
char s[N];
int n,len,id;
int num,ans,cnt=0;
bool f,flag;
ll Hash[N],Pow[N];
int read()
{
    int s=0,t=1; char c;
    while (c<'0'||c>'9'){if (c=='-') t=-1; c=getchar();}
    while (c>='0'&&c<='9'){s=s*10+c-'0'; c=getchar();}
    return s*t;
}
ll readl()
{
    ll s=0,t=1; char c;
    while (c<'0'||c>'9'){if (c=='-') t=-1; c=getchar();}
    while (c>='0'&&c<='9'){s=s*10+c-'0'; c=getchar();}
    return s*t;
}
ll get(int l,int r)
{
    if (l<=r) return (Hash[r]-(ll)Hash[l-1]*Pow[r-l+1]%MOD+MOD)%MOD;
    else return 0;
}
ll find(int x)
{
    ll y1=0,y2=0;
    if (x<=(n>>1)) y1=(get(0,x-1)*Pow[(n>>1)-x]%MOD+get(x+1,n>>1))%MOD,y2=get((n>>1)+1,n-1);
    else y1=get(0,(n>>1)-1),y2=(get((n>>1),x-1)*Pow[n-x-1]%MOD+get(x+1,n-1))%MOD;
    //out(y1); out(y2); writeln;
    if (y1==y2) return y1;
    else return 0;
}
int main()
{
    n=read();
    if (!(n&1)) {
      puts("NOT POSSIBLE");
      return 0;
    }
    else {
      scanf("%s",s);
      len=strlen(s); f=flag=false;
      Pow[0]=1;
      for (int i=1;i<=len;i++)
        Pow[i]=Pow[i-1]*base%MOD;
      for (int i=0;i<len;i++)
        Hash[i]=(Hash[i-1]*base+s[i])%MOD;
      for (int i=0;i<len;i++){
        num=find(i);
        if (num) {
            //out(233); writeln;
          if (!f) ans=num,id=i;
          else if (ans!=num) {
              flag=true; break;
          }
          f=true;
        }
      }
      if (f) {
        if (flag) puts("NOT UNIQUE");
        else {
          for (int i=0;i<len;i++){
            if (i!=id) putchar(s[i]),cnt++;
            if (cnt>=(n>>1)) break;
          }
        }
      }
      else puts("NOT POSSIBLE");
    }
      return 0;
}