2619 三个好朋友
- 1.0 秒
- 131,072.0 KB
- 20 分
- 3级题
有三个好朋友喜欢在一起玩游戏,A君写下一个字符串S，B君将字符串S复制一遍得到两个S拼接而成的字符串T,C君在T的任意位置(包括首尾)插入一个字符得到U.现在你得到了U,请你找出S。
比如得到U串为ABABA。
那么S串有可能是AB，T串为ABAB，之后在最后一个位置插入A，得到ABABA。
S串还有可能是BA，T串为BABA，之后在第一个位置插入A，得到ABABA。
收起
输入
第1行：一个数n,表示U的长度。(1<=n<=200000) 第2行：一个字符串U,保证U由大写字母组成。
输出
输出一行,若S不存在,输出"NOT POSSIBLE".若S不唯一,输出"NOT UNIQUE".否则输出S。
输入样例
7 ABXCABC
输出样例
ABC
不错的Hash题目被我成功的AC，这题对理解字符串Hash有帮助。
对ABXCABC，我们可以暴力枚举每一个位置，关键如何拼接ABXC，我们可以求出AB和C的Hash值，如何拼接成ABC，
AB的Hash：1*P^1+2*P^0,C为3*P^0,AB要拼接在C的前面，需要向高位移一位，给C留出位置来，即
前半部分的Hash值*P^(后半部分字符数量）+后半部分的Hash值
#include<bits/stdc++.h>
const int N = 500000+5;
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
const int P=131;
ULL hashv[N],power[N];
char str[N];
int n;
void calHash()
{power[0]=1;for(int i=1; i<=n; i++){hashv[i]=hashv[i-1]*P+(str[i]-'A'+1);power[i]=power[i-1]*P;}
}
ULL getHash(int l,int r)
{if(r>=l)return hashv[r]-hashv[l-1]*power[r-l+1];elsereturn 0;
}
set<ULL> s;
int main()
{scanf("%d",&n);scanf("%s",str+1);calHash();if(n%2==0){printf(("NOT POSSIBLE\n"));return 0;}int len=(n-1)/2;int pos;for(int i=1; i<=len+1; i++){//cout<<getHash(len+2,n)<<" "<<getHash(1,i-1)*power[len-(i-1)]<<" "<<getHash(i+1,1+len)<<endl;if(getHash(len+2,n)==getHash(1,i-1)*power[len-(i-1)]+getHash(i+1,len+1)){pos=i;s.insert(getHash(len+2,n));}if(s.size()>=2)break;}if(s.size()>=2){printf("NOT UNIQUE\n");return 0;}for(int i=len+2; i<=n; i++){//cout<<getHash(len+2,n)<<" "<<getHash(1,i-1)*power[len-(i-1)]<<" "<<getHash(i+1,1+len)<<endl;if(getHash(1,len)==getHash(len+1,i-1)*power[len-(i-(len+1))]+getHash(i+1,n)){pos=i;s.insert(getHash(1,len));}if(s.size()>=2)break;}if(s.size()==1){int t=0;for(int i=1;i<=len+1;i++){if(pos!=i){t++;printf("%c",str[i]);if(t==len)break;}}return 0;}else if(s.size()==0){printf(("NOT POSSIBLE\n"));return 0;}else{printf("NOT UNIQUE\n");return 0;}return 0;
}