C++(g++ 7.5.0) 解法, 执行用时: 62ms, 内存消耗: 34576K, 提交时间: 2023-05-11 23:35:41

#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;

#define N 2000100
#define ll unsigned long long
#define base 233

ll h[N], p[N], ha;
char s[N], ans[N];
int n;
ll t1 = 0, t2 = 0, t = 0;

ll get_hash(int l, int r) {return h[r] - h[l - 1] * p[r - l + 1];}

bool check(int x) {
    if(x > n / 2) t1 = get_hash(1, n / 2), t2 = get_hash(n / 2 + 1, x - 1) * p[n - x] + get_hash(x + 1, n);
    else t1 = get_hash(n / 2 + 2, n), t2 = get_hash(1, x - 1) * p[n / 2 - x + 1] + get_hash(x + 1, n / 2 + 1);
    return t1 == t2;
}

int main() {
    p[0] = 1;
    for(int i = 1; i < 2000000; ++i) p[i] = p[i - 1] * base;
    scanf("%d%s", &n, s + 1);
    if(!(n & 1)) return puts("NOT POSSIBLE"), 0;
    for(int i = 1; i <= n; ++i) {
        h[i] = h[i - 1] * base + (ll)(s[i]);
    }
    int pos = 0;
    for(int i = 1; i <= n; ++i) {
        if(check(i)) {
            if(!t) t = t1;
            else if(t != t1) return puts("NOT UNIQUE"), 0;
            pos = i;
        }
    }
    if(!pos) return puts("NOT POSSIBLE"), 0;
    if(pos <= n / 2) for(int i = n / 2 + 2; i <= n; ++i) putchar(s[i]);
    else for(int i = 1; i <= n / 2; ++i) putchar(s[i]);
}

C++14(g++5.4) 解法, 执行用时: 37ms, 内存消耗: 21960K, 提交时间: 2019-11-17 22:27:31

#include<bits/stdc++.h>
using namespace std;
const int P = 1e9+7;

int main() {
  ios::sync_with_stdio(false);
  int N; cin >> N;
  string s; cin >> s;
  vector<unsigned> H(N+1); for (int i = 0; i < N; i++) H[i+1] = H[i] * P + s[i];
  vector<unsigned> B(N+1); for (int i = 0; i <= N; i++) B[i] = i?B[i-1]*P:1;
  int ans = -1;
  int ans_i = -1;
  for (int i = 1; i <= N; i++) {
    unsigned ALL, HALF;
    ALL = (H[N] - H[i] * B[N-i])*P + H[i-1]*B[N-i+1];
    if (i <= N / 2) HALF = H[N] - H[N/2+1] * B[N/2];
    else  HALF = H[N/2];
    if (HALF*P+HALF*B[N/2+1] == ALL) {
      if (ans != -1 && ans != ALL) {
        cout << "NOT UNIQUE" << endl;
        return 0;
      } else ans = ALL, ans_i = i;  
    }
  }
  
  if (ans_i == -1)  cout << "NOT POSSIBLE" << endl;
  else if (ans_i <= N / 2) cout << s.substr(N/2+1) << endl;
  else cout << s.substr(0, N/2) << endl;
}

C++(clang++11) 解法, 执行用时: 41ms, 内存消耗: 5356K, 提交时间: 2022-02-02 22:16:36

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

int n,sum,m,flag1,flag2;
string s,s1,s2;

int main()
{
	scanf("%d",&n);
	if(!(n&1)){printf("NOT POSSIBLE\n");return 0;}
    cin>>s;
    m=n/2;
    s1=s.substr(0,m);
    for(int i=m;i<n&&sum<m;i++)
    	if(s[i]==s1[sum]) sum++;
    if(sum==m) flag1=1;
    s2=s.substr(n-m,m);
    sum=0;
    for(int i=0;i<n-m&&sum<m;i++)
    	if(s[i]==s2[sum]) sum++;
    if(sum==m) flag2=1;
    if(flag1&&flag2&&s1!=s2) printf("NOT UNIQUE\n");
    else if(!flag1&&!flag2) printf("NOT POSSIBLE\n");
    else if(flag1) cout<<s1<<endl;
    else cout<<s2<<endl;
	return 0;
}