方法很多,hash,双hash(个人想到一种三hash),挂链,还有STL;
map 乱搞 CODE
#include<iostream> #include<map> #include<string> using namespace std; int n,ans; string s; map <string,bool> ma; int main() { cin>>n; while (n--) { cin>>s; if (ma[s]) continue; ma[s]=1; ans++; } cout<<ans; return 0; }
hash就是将一个字符串映射成一个数。中间的方法有很多,不停地乘上一个seed然后%一下。
然后单hash炸了。
果断双hash!(hash twice)
#include<iostream> #include<string> using namespace std; typedef long long LL; LL n,ans; const LL seed1=167,mod1=2333333,seed2=259,mod2=1000007; string s; bool f1[mod1+5],f2[mod2+5]; inline LL hash1(string s) { LL tot=1; for (int i=0;i<s.size();++i) tot=(tot*seed1+s[i])%mod1; return tot; } inline LL hash2(string s) { LL tot=1; for (int i=0;i<s.size();++i) tot=(tot*seed2+s[i])%mod2; return tot; } int main() { cin>>n; while (n--) { cin>>s; LL k1=hash1(s),k2=hash2(s); if (f1[k1]&&f2[k2]) continue; f1[k1]=f2[k2]=1; ans++; } cout<<ans; return 0; }