关于本题与字符串哈希
查看原帖
关于本题与字符串哈希
556545
_anll_楼主2024/8/7 15:06

rt,没看到题解区有这个做法,本蒟蒻想尝试但是 WA 了然后没看出来为什么会 WA。想问问:

  1. 为什么没有大佬写字符串哈希,是因为这道题不适合吗

  2. 如果这道题字符串哈希能过的话跪求大佬帮我看看代码orz

#include<iostream>
#include<algorithm>
#include<unordered_map>
#define int long long
using namespace std;
const int N=1e4+5,P=8281027,mod=1e9+7;
int t,n;
string S[N];
unordered_map<int,int> mo;
bool cmp(string a,string b){
	return a.size()<b.size();
}
bool work(string s,int a=0){
	for(int i=0;i<s.size();i++){
		a=((a*P)%mod+s[i])%mod;
		if(mo[a]) return 1;
	}
	mo[a]++;return 0;
}
void solve(){
	cin>>n;mo.clear();
	for(int i=1;i<=n;i++) cin>>S[i];
	sort(S+1,S+1+n,cmp);
	for(int i=1;i<=n;i++){
		if(work(S[i])){cout<<"NO"<<endl;return;}
	}
	cout<<"YES"<<endl;
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>t;while(t--) solve();
	return 0;
}
2024/8/7 15:06
加载中...