看了下题解，全是哈希。

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

思路

由题意可知 $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;
}

#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ULL;
const int N = 2110000;
ULL f[N], d[N];
char s[N];

ULL Hash(int l, int r) { return f[r] - f[l - 1] * d[r - l + 1]; }

ULL Hash12(int l1, int r1, int l2, int r2)
{
    return Hash(l1, r1) * d[r2 - l2 + 1] + Hash(l2, r2);
}

int main()
{
    int n;
    scanf("%d%s", &n, s + 1);
    if (n % 2 == 0) {
        printf("NOT POSSIBLE\n");
        return 0;
    }
    d[0] = 1;
    for (int i = 1; i <= n; i++)
        d[i] = d[i - 1] * 131;
    for (int i = 1; i <= n; i++)
        f[i] = f[i - 1] * 131 + s[i];
    int p = 0;
    ULL ans = 0;
    for (int i = 1; i <= n; i++) {
        if (i <= n / 2) {
            if (Hash12(1, i - 1, i + 1, n / 2 + 1) == Hash(n / 2 + 2, n)) {
                if (p == 0)
                    p = i, ans = Hash(n / 2 + 2, n);
                else {
                    if (ans == Hash(n / 2 + 2, n))
                        continue;
                    else {
                        printf("NOT UNIQUE\n");
                        return 0;
                    }
                }
            }
        } else if (i == n / 2 + 1) {
            if (Hash(1, n / 2) == Hash(n / 2 + 2, n)) {
                if (p == 0)
                    p = i, ans = Hash(n / 2 + 2, n);
                else {
                    if (ans == Hash(n / 2 + 2, n))
                        continue;
                    else {
                        printf("NOT UNIQUE\n");
                        return 0;
                    }
                }
            }
        } else {
            if (Hash(1, n / 2) == Hash12(n / 2 + 1, i - 1, i + 1, n)) {
                if (p == 0)
                    p = i, ans = Hash(1, n / 2);
                else {
                    if (ans == Hash(1, n / 2))
                        continue;
                    else {
                        printf("NOT UNIQUE\n");
                        return 0;
                    }
                }
            }
        }
    }

    if (p == 0)
        printf("NOT POSSIBLE\n");
    else {
        if (p <= n / 2 + 1)
            for (int i = n / 2 + 2; i <= n; i++)
                printf("%c", s[i]);
        else
            for (int i = 1; i <= n / 2; i++)
                printf("%c", s[i]);
        printf("\n");
    }
    return 0;
}