题面

大秦为你打开题目传送门

题目描述

有三个好朋友喜欢在一起玩游戏,A君写下一个字符串S,B君将其复制一遍得到T,C君在T的任意位置(包括首尾)插入一个字符得到U.现在你得到了U,请你找出S.

思路

我们直接，大力枚举这个插入的字符，然后大力哈希判断即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include<bits/stdc++.h>
using namespace std;

typedef unsigned long long ull;

const int N = 2e6 + 10;
const int B = 31;
ull Power[N];

int n;
string s;

ull hsh[N];
inline ull Hash(int l, int r) { 
    return l <= r ? hsh[r] - hsh[l - 1] * Power[r - l + 1] : 0; 
}

inline void Input() {
	cin >> s;
	s = ' ' + s;
}

inline void Init() {
	Power[0] = 1;
	for(int i = 1; i <= n; i++) {
		Power[i] = Power[i - 1] * B;
		hsh[i] = hsh[i - 1] * B + (s[i] - 'A');
	}
}

inline void Work() {
	n = s.length() - 1;
//	cout << "Len: " << n << endl;
	if(n % 2 == 0) {
		printf("NOT POSSIBLE\n");
		return ;
	}
	Init();
	set<string >st;
	for(int i = 1; i <= n; i++) {
		ull hshL = Hash(1, n / 2), hshR = Hash(n / 2 + 2, n);
		int flag = 0;
	//	cout << "Pos: " << i << endl;
		if(i != n / 2 + 1) {
			if(i <= n / 2) {
			//	cout << "L\n";
			//	cout << Hash(1, i - 1) * Power[n / 2 - i + 1] << ' ' << Hash(i + 1, n / 2 + 1) << endl;
				hshL = Hash(1, i - 1) * Power[n / 2 - i + 1] + Hash(i + 1, n / 2 + 1);
				flag = 1;
			}
			else {
			//	cout << "R\n";
			//	cout << Hash(n / 2 + 1, i - 1) * Power[n - i + 1] << ' ' << Hash(i + 1, n) << endl;	
				hshR = Hash(n / 2 + 1, i - 1) * Power[n - i] + Hash(i + 1, n);
			}
		}
	//	cout << hshL << ' ' << hshR << endl;
		if(hshL == hshR) {
		//	cout << hshL << ' ' << hshR << endl;
			if(flag == 0) st.insert(s.substr(1, n / 2));
			else st.insert(s.substr(n / 2 + 2));
		}
	}
	if(st.empty()) printf("NOT POSSIBLE\n");
	else if(st.size() > 1) printf("NOT UNIQUE\n");
	else cout << *st.begin();
}

int main() {
	int T = 1;
	while(T--) {
		Input();
		Work();
	}
	return 0;
}