这题哈希不行吗
查看原帖
这题哈希不行吗
1394628
Moon_Lord楼主2024/9/19 17:15

本题显然可以使用 Trie,但是试了一下哈希的做法一直 WA,感觉实现没问题,是模数的问题吗?

#include<iostream>
#include<algorithm>
#include<unordered_map>
#define int long long
using namespace std;
const int N = 2e5 + 5, P = 8281027, mod = 1e11 + 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 true;
	}
	mo[a]++;
	return false;
}
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/9/19 17:15
加载中...