题意

给一个字符串，看看删去一个字符后前半段和后半段相不相等。

思路

首先，字符串长度一定得是奇数，因为字符串删掉一个字符后前后长度要一样。这个一看就知道。

然后开始做题，我们用哈希做。

这个新加入的字符要么在前，要么在后。所以找一个字符删掉然后比较前后是否相等就行了。

这里分前后找，前面找到一个后就直接 break，然后找下一段（找到就代表那一段至少有一个符合要求的字符）

但这里要看结果是否唯一，所以要检测有没有多个答案。

总结：

• 给的字符串的长度一定是奇数
• 前面找到直接到后面找
• 检测是否有多个答案

代码

#include <bits/stdc++.h>
using namespace std;
const int N = 2000005,BASE = 2617;
int p[N] = {1},h[N],l1,l2,cnt;
int sec(int l,int r){	// 区间哈希
	return h[r] - h[l - 1] * p[r - l + 1];
}
int sub(int l,int r,int x){	// 减去其中一个字母
	return sec(l,x - 1) * p[r - x] + sec(x + 1,r);
}
signed main(int argc, char **argv){
	for (int i = 1;i <= N;i++)	p[i] = p[i - 1] * BASE;
	int n;string s,a,b/*不是骂人*/;char c;
	cin >> n >> s;
	if (n % 2 == 0){
		printf("NOT POSSIBLE");
		return 0;
	}
	int mid = n + 1 >> 1;
	for (int i = 1;i <= n;i++){	// 算好整个字符串的哈希
		char x = s[i - 1];
		h[i] = h[i - 1] * BASE + (x - 'A' + 1);
	}

	l1 = sec(1,mid - 1);	// 前半段
	a = s.substr(0,mid - 1);	// 前半段少一个字符的字符串
	for (int i = mid;i <= n;i++){	// 暴搜
		l2 = sub(mid,n,i);
		if (l1 == l2){
			cnt++;
			c = 'a';
			break;
		}
	}
	l2 = sec(mid + 1,n);	// 后半段
	b = s.substr(mid,n);	// 后半段的字符串
	for (int i = 1;i <= mid;i++){	// 暴搜
		l1 = sub(1,mid,i);
		if (l1 == l2){
			cnt++;
			c = 'b';
			break;
		}
	}

	// 答案为 0（没有）
	if (!cnt)	printf("NOT POSSIBLE");
	// 答案唯一，或添加的字符刚好在中间
	else if (cnt == 1 || a == b)	cout << (c == 'a'?a:b);
	// 答案不唯一
	else	printf("NOT UNIQUE");
	return 0;
}

参考与鸣谢

参考了Mars_Dingdang的这篇题解

题意

题目说的已经很清楚了

有一个字符串 $S$，对他进行操作：

1. 将 $S$ 复制为两份，存在字符串 $T$ 中
2. 在 $T$ 的某一位置上插入一个字符，得到字符串 $U$

现在给定 $U$，求 $S$。

思路

首先要判断长度是不是奇数,应为只有奇数才说明可能有插入的那一个字符

分两段判断

由题意可知 $N$ 得为奇数，$S$才存在，所以先特判 $N$ 为偶数的情况。

由题意可知 $S$ 的长度为 $\lfloor\frac{N}{2}\rfloor$， 设 $S$ 的长度为 $M$。

因为只插入一个字符，所以如果存在 $S$，则 $U$ 的前 $M$ 个字符或后 $M$ 个字符中一定有一边是$S$。

所以可以用 substr 函数分别截取前 $M$ 个字符和后 $M$ 个字符，再依次匹配检查是否合法。

代码

#include<iostream>
#include<string>
using namespace std;
int n;
string u;
int main()
{
    cin>>n>>u;
    if(n%2==0)//只有奇数个字符才有可能有S
    {
        cout<<"NOT POSSIBLE";
        return 0;
    }
    int m=n/2;
    bool fa=0,fb=0;
    string a=u.substr(0,m);
    int j=0;
    for(int i=m;i<n && j<m;i++)//前一段
        if(u[i]==a[j])
            j++;
    if(j==m)
        fa=1;
    string b=u.substr(n-m,m);
    j=0;
    for(int i=0;i<n-m && j<m;i++)//后一段
        if(u[i]==b[j])
            j++;
    if(j==m)
        fb=1;
    if(fa==0 && fb==0)//不存在
        cout<<"NOT POSSIBLE";
    else if(fa && fb && a!=b)
        cout<<"NOT UNIQUE";
    else if(fa)
        cout<<a;
    else
        cout<<b;
    return 0;//完结散花
}

题意

题目说的已经很清楚了

有一个字符串 $S$，对他进行操作：

1. 将 $S$ 复制为两份，存在字符串 $T$ 中
2. 在 $T$ 的某一位置上插入一个字符，得到字符串 $U$

现在给定 $U$，求 $S$。

思路

思路来源于这位 luogu 大佬的题解

首先要判断长度是不是奇数,应为只有奇数才说明可能有插入的那一个字符

分两段判断

题解原文思路

由题意可知 $N$ 得为奇数，$S$才存在，所以先特判 $N$ 为偶数的情况。

由题意可知 $S$ 的长度为 $\lfloor\frac{N}{2}\rfloor$， 设 $S$ 的长度为 $M$。

因为只插入一个字符，所以如果存在 $S$，则 $U$ 的前 $M$ 个字符或后 $M$ 个字符中一定有一边是$S$。

所以可以用 substr 函数分别截取前 $M$ 个字符和后 $M$ 个字符，再依次匹配检查是否合法。

代码

#include<iostream>
#include<string>
using namespace std;
int n;
string u;
int main()
{
    cin>>n>>u;
    if(n%2==0)//只有奇数个字符才有可能有S
    {
        cout<<"NOT POSSIBLE";
        return 0;
    }
    int m=n/2;
    bool fa=0,fb=0;
    string a=u.substr(0,m);
    int j=0;
    for(int i=m;i<n && j<m;i++)//前一段
        if(u[i]==a[j])
            j++;
    if(j==m)
        fa=1;
    string b=u.substr(n-m,m);
    j=0;
    for(int i=0;i<n-m && j<m;i++)//后一段
        if(u[i]==b[j])
            j++;
    if(j==m)
        fb=1;
    if(fa==0 && fb==0)//不存在
        cout<<"NOT POSSIBLE";
    else if(fa && fb && a!=b)
        cout<<"NOT UNIQUE";
    else if(fa)
        cout<<a;
    else
        cout<<b;
    return 0;//完结散花
}