写在前面
P6739 [BalticOI 2014 Day1] Three Friends
听说这题可以用比较暴力的做法过,比如 (string) 里面自带的 (substr) ,可以看这位大佬的提交记录
模数不要用 (49999) ,会被卡, (1e9+9) 才是真爱
Solution
何为字符串哈希(可跳过):
由于字符串是具有前后关系的,可以按下述方法构造:
选取两个合适的互质常数 (b) 和 (h (b < h)), 假设有一个字符串 (C = c_1c_2···c_m),那么我们定义哈希函数:
考虑递推实现,设 (H(C, k)) 为前 (k) 个字符构成的字符串的哈希值,则:
通常,题目要求的是判断主串的一段字符与另一个匹配串是否匹配,即判断字符串 (C = c_1c_2···c_m) 从位置 (k + 1) 开始的长度为 (n) 的子串 (C^{'} = c_{k + 1}c_{k + 2}···c_{k + n}) 的哈希值与另一匹配串 (S = s_1s_2···s_n) 的哈希值是否相等,则:
只要预求得 (b^{n}) ,就能 (O(1)) 判断了
可以预处理出所有 (b^{n}) 存在 (Pow) 数组里
观察目标串 (U) 的构造方式,发现如果 (N) 是偶数,一定无法构造
然后考虑枚举删除每一个字符,再将剩下的字符串均分判断哈希值是否相等
假设删去的字符在前半段,那么后半段的一定是原字符串 (S),如果在后半段,那么前半段一定是原字符串 (S) ,
所以可以分开枚举,并且预处理出对应的原字符串
那么删掉一个字符后,剩下的两段怎么合并呢?以样例字符串为例:
假设枚举到 (X)
那么原字符串为 (ABC),前面要合并的两段字符串是 (AB),(C)
如果朴素计算这两个串的哈希值及原字符串哈希值,计算过程如下:
所以不难看出 (ABC = AB * b^{1} + C)
对这个结论进行推广,对于字符串 (X),删掉其中一个字符后,分成两个字符串(X_1,X_2),有
根据这个公式去进行合并,然后比较两个字符串哈希值是否相同
然后这就可以了吗? 不不不
看这个样例
13
AABCABCABCABC
我们会发现删掉第一个和第二个字符都可以,但得到的原串都是 (ABCABC)
所以注意开个map判重即可
如果还A不了,兄弟,改个模数试试吧
Code
/*
Work by: Suzt_ilymics
Knowledge: ??
Time: O(??)
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
#define LL long long
#define orz cout<<"lkp AK IOI!"<<endl
using namespace std;
const int MAXN = 2e6+10;
const int INF = 1;
const int mod = 1e9+9;
const int b = 7;
int len, cnt = 0;
char s[MAXN];
LL Pow[MAXN], Pow2, sum, H[MAXN], wz;
map<LL, LL> Map;
int read(){
int s = 0, f = 0;
char ch = getchar();
while(!isdigit(ch)) f |= (ch == '-'), ch = getchar();
while(isdigit(ch)) s = (s << 1) + (s << 3) + ch - '0' , ch = getchar();
return f ? -s : s;
}
int main()
{
len = read();
if(len % 2 == 0) {
printf("NOT POSSIBLE");
return 0;
}
cin>>(s + 1);
// for(int i = 1; i <= len; ++i) {
// cout<<s[i]<<" ";
// }
// cout<<"
";
Pow[0] = 1;
for(int i = 1; i <= len; ++i){
Pow[i] = Pow[i - 1] * b % mod;
H[i] = (H[i - 1] * b % mod + s[i]) % mod;
}
sum = (H[len] - H[len / 2 + 1] * Pow[len / 2] % mod + mod) % mod; //后半段的哈希值
for(int i = 1; i <= len / 2 + 1; ++i){
LL pre = H[i - 1] * Pow[len / 2 + 1 - i] % mod;//删掉枚举字符后的剩余字符串的哈希值
if(Map[sum] == 0 && sum == (H[len / 2 + 1] - H[i] * Pow[len / 2 + 1 - i] % mod + pre + mod) % mod){//算出后面那一段并进行拼接
cnt++;
Map[sum]++;
wz = i;
}
}
// cout<<cnt<<"lkp
";
sum = H[len / 2];//前半段的哈希值
for(int i = len / 2 + 2; i <= len; ++i){
LL pre = (H[i - 1] - H[len / 2] * Pow[i - len / 2 - 1] % mod + mod) % mod * Pow[len - i] % mod;//删掉枚举字符后的剩余字符串的哈希值
if(Map[sum] == 0 && sum == (H[len] - H[i] * Pow[len - i] % mod + pre + mod) % mod){//算出后面那一段并进行拼接
cnt++;
Map[sum]++;
wz = i;
}
}
// cout<<cnt<<"zsf
";
if(cnt == 0) printf("NOT POSSIBLE");
else if(cnt == 1) {
if(wz <= len / 2) for(int i = len / 2 + 2; i <= len; ++i) cout<<s[i];
else for(int i = 1; i <= len / 2; ++i) cout<<s[i];
}
else printf("NOT UNIQUE");
return 0;
}