rt,没看到题解区有这个做法,本蒟蒻想尝试但是 WA 了然后没看出来为什么会 WA。想问问:
为什么没有大佬写字符串哈希,是因为这道题不适合吗
如果这道题字符串哈希能过的话跪求大佬帮我看看代码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;
}