题解 P6739 【[BalticOI 2014 Day1] Three Friends】
Mars_Dingdang
2020-12-01 17:45:14
这一题用哈希就可以水掉了。需掌握求一个字符串区间哈希值的做法。
## 题目大意
**尊重原题**：有 $3$ 个好朋友喜欢一起玩游戏，$A$ 君写下了一个字符串 $S$，$B$ 君将其复制一遍得到 $T$，$C$ 君在其任意位置（**包括首尾**）插入一个字符得到一个字符串 $U$。现在你得到了 $U$，请找出 $S$。
**简化版**：有一个字符串 $S$，对其进行操作：
- 将 $S$ 复制为两份，存在字符串 $T$ 中；
- 在 $T$ 的某一位置上插入一个字符，得到字符串 $U$。
现在给定 $U$，求 $S$。
## 大体思路
#### 前置芝士：字符串哈希
如果对字符串哈希不甚了解，请自行参考 [这题](https://www.luogu.com.cn/problem/P3370)。
此处介绍的，即是最常见的一种哈希：进制哈希。进制哈希的核心便是给出一个固定进制 $base$，将一个串的每一个元素看做一个进制位上的数字，所以这个串就可以看做一个 $base$ 进制的数，那么这个数就是这个串的哈希值；则我们通过比对每个串的的哈希值，即可判断两个串是否相同。
首先选择两个质数。我选择 $22783$ 作为底数（这是我们班一个人的学号），并用 `unsigned long long` 自然溢出的特性作为模数。下方所有变量未经特殊说明均为无符号长整形。（详见代码）
接下来进行预处理：用一个数组 $pre_k$ 表示 $base^k$，并滚动处理字符串哈希值 $H_i=H_{i-1}\times base + S_i$，其中 $H_i$ 表示哈希值，$S_i$ 为字符串中的元素。
```cpp
pre[0]=1;//边界条件：base 的 0 次方等于一。
for(int i= 1;i<=n;i++) {
pre[i]=pre[i-1]*22783;//记录 pre 数组
h[i]=h[i-1]*22783+(s[i]-'A'+1);//滚动处理哈希值
}
```
在得到字符串哈希值后，如何求区间的哈希值呢？其实类似前缀和的思想，$hash[l,\ r]=H_r-H_{l-1}\times pre_{r-l+1}$。显然单纯的相减是不可取的，因此需要将区间前一项乘以底数的区间长度次幂，以求得字符串的区间哈希值。
而题目是插入了一个字符，因此我们逆向处理时需枚举删去一个字符的哈希值。类似上方，删去第 $x$ 个字符后的哈希值为 $hash[1,x-1]\times pre_{r-x} + hash[x+1,r]$。对于整个字符串而言，$l=1,r=n$。
```cpp
inline unsigned long long check(int l, int r) {
return h[r] - h[l - 1] * pre[r - l + 1];
}//区间哈希值
inline unsigned long long sum(int l, int r, int k) {
return check(l, k - 1) * pre[r - k] + check(k + 1, r);
}//删去第 k 个字符
```
#### 本题详解
首先一个很显然的结论：由于 $U$ 串是 $S$ 串复制两次后插入一个字符所得，因此长度必然为奇数。所以特判：若 $n$ 为偶数则直接输出 `NOT POSSIBLE`。
接下来，将得到的字符串分成两部分 $1\sim mid,\ mid+1\sim n$，并分别记录这两段的哈希值。然后对于 $mid+1\sim n$，枚举删去 $1\sim mid$ 中的字符，若所得字符串与后半段相等则答案数 $ans+1$ 并跳出循环。反之亦然。
然后进行判断：
- 若答案数为零，则无解，输出 `NOT POSSIBLE`。
- 若答案数为一，或删去字符后的两串相等，则输出删去后不为空的字符串（即所求的 $S$）。
- 否则说明答案不唯一，输出 `NOT UNIQUE`。
## 完整代码
```cpp
#include<bits/stdc++.h>
using namespace std;
#define maxn 2000002
string a, b, c, d;
int n, mid, l1, l2, h[maxn], pre[maxn], ans;
char s[maxn];
inline unsigned long long check(int l, int r) {
return h[r] - h[l - 1] * pre[r - l + 1];
}//区间哈希值
inline unsigned long long sum(int l, int r, int k) {
return check(l, k - 1) * pre[r - k] + check(k + 1, r);
}//删去字符
int main() {
scanf("%d%s",&n,s+1);
mid=(n+1)>>1;
if (!(n&1)){
printf("NOT POSSIBLE");
return 0;
}//特判
pre[0]=1;
for(int i= 1;i<=n;i++) {
pre[i]=pre[i-1]*22783;
h[i]=h[i-1]*22783+(s[i]-'A'+1);
}//预处理
l1=check(mid+1,n);
for(int i=mid+1;i<=n;i++) a.push_back(s[i]);
for(int i=1;i<=mid;i++) {
l2=sum(1,mid,i);
if (l1==l2){
ans++;
c=a;
break;
}
}
l2=check(1,mid-1);
for(int i=1;i<mid;i++) b.push_back(s[i]);
for(int i=mid;i<=n;i++) {
l1=sum(mid,n,i);
if(l1==l2) {
ans++;
d=b;
break;
}
}//枚举
if (!ans)
printf("NOT POSSIBLE");
else if (ans == 1 || c == d)
cout << (c.size() ? c : d);
else printf("NOT UNIQUE");//判断输出
return 0;
}
```
## 后记
今天 CSP2020 出成绩，普及组正常 1=，提高组因为 T3 加了 `ios::sync_with_stdio(0);` 语句而抱灵，导致 1= 没了，悲痛。
希望 NOIp rp++！