hash求救,WA了几个点
查看原帖
hash求救,WA了几个点
227824
JK_LOVER楼主2020/8/8 09:01
#include<bits/stdc++.h>
using namespace std;
#define int long long 
const int N = 2e6+100,Mod = 998244353,Base = 213; 
int hash[N],n,Pow[N],Ans = 0,pos,vis[30];
char ch[N];
int Sum(int l,int r){
	if(l > r) return 0;
//	cout<<((hash[r] - (hash[l-1] * Pow[r-l+1])%Mod)%Mod+Mod)%Mod<<endl;
	return ((hash[r] - (hash[l-1] * Pow[r-l+1])%Mod)%Mod+Mod)%Mod;
}
bool Same(int Mid){
	if(Mid < (n+1)/2){
		int L = (Sum(1,Mid-1) * Pow[(n+1)/2-Mid] % Mod + Sum(Mid+1,(n+1)/2)%Mod) % Mod;
		int R = Sum((n+1)/2+1,n);
//		cout<<L<<" "<<R<<endl;
		return L == R;
	}
	if(Mid == (n+1)/2){
		return Sum(1,Mid-1) == Sum(Mid+1,n);
	}
	if(Mid > (n+1)/2){
		int L = Sum(1,(n+1)/2-1)%Mod;
		int R = (1LL*Sum((n+1)/2,Mid-1) * Pow[n - Mid] % Mod + Sum(Mid+1,n)+Mod)% Mod;
		return L == R;
	}
}
signed main()
{
	int jud = 0;
	cin>>n;
	cin>>ch+1;
//	if(!(n&1)) {printf("NOT POSSIBLE\n");return 0;}
	Pow[0] = 1;hash[0] = 0;
	for(int i = 1;i <= n;i++){
		hash[i] = (1LL*hash[i-1]*Base%Mod+(1LL*ch[i]-'A'+1))%Mod;
		Pow[i] = (1LL*Pow[i-1]*Base)%Mod;
//		cout<<hash[i]<<endl;
	}
	for(int i = 1;i <= n;i++){
		if(Same(i)){
			Ans++;
			pos = i;
			if(vis[ch[i]-'A'] && vis[ch[i]-'A']!=i-1) jud = 1;
			if(!vis[ch[i]-'A']) vis[ch[i]-'A'] = i;
		}
	}
	if(!Ans) cout<<"NOT POSSIBLE"<<endl;
	if(Ans>1 && jud) cout<<"NOT UNIQUE"<<endl;
	if(Ans == 1){
		if(pos < (n+1)/2){
			for(int i = (n+1)/2+1;i <= n;i++) printf("%c",ch[i]);
		}
		if(pos == (n+1)/2){
			for(int i = 1;i < pos;i++) printf("%c",ch[i]);
		}
		if(pos > (n+1)/2){
			for(int i = 1;i < (n+1)/2;i++) printf("%c",ch[i]);
		}
		cout<<endl;
	}
	return 0;
}
2020/8/8 09:01
加载中...