Luogu P3370 【模板】字符串哈希

　　方法很多，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;
}