本题显然可以使用 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;
}