加密传输（字符串哈希）

加密传输

时间限制：1秒        内存限制：128M

题目描述：

小可和他的朋友进行加密的消息传递，记原消息为S，加密分为两步：

1.对S进行复制，形成一个新字符串T，即T=S+S
2.在T的某一位置插入一个字符，得到新字符串U

现在小可的朋友拿到了U，请解析U得到S

输入格式：

第一行：输入一个整数 n 代表加密后的消息 U 的长度。
第二行：输入一个长度为 n 的字符串

对于25%的数据 n ≤ 3000
对于100%的数据 n ≤ (2*10^6 +1)

输出格式：

如果不能通过上述的步骤从 S 推到 U，输出 NOT POSSIBLE。
如果从 U 得到的 S 不是唯一的，输出 NOT UNIQUE。
否则，输出一个字符串 S 。

输入样例1：

1. 7
2. ABXCABC

输出样例1：

1. ABC

输入样例2：

1. 6
2. ABCDEF

输出样例2：

1. NOT POSSIBLE

输入样例3：

1. 9
2. ABABABABA

输出样例3：

1. NOT UNIQUE

讲解

经过哈希可以确定一个字符串

所以，我们把字符串删除后分成两半后

看两段的哈希值是否相同，这样就可以O（1）的比较了

#include<iostream>
#include<string>
#include<map> 
using namespace std;
const int base=400031;
int n,mid;
string s;
map<long long,int>vis;
long long power[2000005],hs[2000005],rt,lt,tmp;
int gethash(int l,int r){
	return hs[r]-hs[l-1]*power[r-l+1];
}
int delhash(int l,int r,int pos){
	return gethash(l,pos-1)*power[r-pos]+gethash(pos+1,r);
}
bool judge(int pos){
	if(pos==mid){
		lt=gethash(1,pos-1);
		rt=gethash(pos+1,n);
		return lt==rt;
	}
	if(pos<mid){
		lt=delhash(1,mid,pos);
		rt=gethash(mid+1,n);
		return lt==rt;
	}
	lt=gethash(1,mid-1);
	rt=delhash(mid,n,pos);
	return lt==rt;
}
int main(){
	cin>>n>>s;
	s="0"+s;
	mid=(n+1)>>1;
	power[0]=1;
	for(int i=1;i<=n;i++){
		power[i]=power[i-1]*base;
		hs[i]=hs[i-1]*base+s[i];
	}
	int mark,ans=0;
	for(int i=1;i<=n;i++)
		if(judge(i)){
			mark=i;
			if(mark<=mid){
				tmp=rt;
			}else{
				tmp=lt;
			}
			if(vis[tmp]>0)
				continue;
			vis[tmp]=1;
			ans++;
		}
	if(ans>1){
		puts("NOT UNIQUE");
		return 0;
	}
	if(ans==0){
		puts("NOT POSSIBLE");
		return 0;
	}
	if(mark<=mid){
		cout<<s.substr(mid+1);
	}else{
		cout<<s.substr(1,mid-1);
	}
	return 0;
}