题解 P3370 【【模板】字符串哈希】

Decide · 2017-04-27 15:22:53 · 题解

不知道有没有一样的题解啊。。。就随便发一下。。。hash+map，map直接水过，用一个map从unsigned long long的字符串hash后的值映射到一个int整数型表示是否存在就行了。。头文件我就不补了

typedef unsigned long long ull;
ull x = 45321;
map<ull,int> vis;
int ans = 0,n;
char s[1005];
ull hash(char *s)
{
    int len  = strlen(s);
    ull res = 0;
    for(int i = 0;i<len;i++)
    {
        res+=s[i];
        res*=x;
    }
    return res;
}
int main()
{
    //freopen("std.in","r",std5in);
    //freopen("std.out","w",stdout);
    cin>>n;
    for(int i = 1;i<=n;i++)
    {
        cin>>s;
        ull tmp = hash(s);
        if(vis[tmp]==1) continue;
        vis[tmp] = 1;
        ans++;
    }
    cout<<ans<<endl;
    return 0;
}