自动搬运

查看原文

来自洛谷，原作者为

	LongDouble AFOed in 2022

搬运于2025-08-24 22:23:30，当前版本为作者最后更新于2020-08-09 09:48:28，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

看了下题解，全是哈希。

这里写一个更简单的做法。

思路

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

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

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

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

代码

#include <bits/stdc++.h>
using namespace std;
int n, m, a1, a2;
string u, s1, s2;

int main()
{
	scanf("%d", &n);
	if (n % 2 == 0)
	{
		printf("NOT POSSIBLE\n");
		return 0;
	}
	cin >> u;
	m = n / 2;
    
	s1 = u.substr(0, m); //匹配检查前M个字符
	int j = 0;
	for (int i = m; i < n && j < m; i++) 
		if (u[i] == s1[j]) j++;
	if (j == m) a1 = 1;
    
	s2 = u.substr(n - m, m); //匹配检查后M个字符
	j = 0;
	for (int i = 0; i < n - m && j < m; i++)
		if (u[i] == s2[j]) j++;
	if (j == m) a2 = 1;
    
	if (!a1 && !a2) printf("NOT POSSIBLE\n");
	else if (a1 && a2 && s1 != s2) printf("NOT UNIQUE\n");
	else if (a1) cout << s1 << endl;
		else cout << s2 << endl;
	return 0;
}