当前位置 : 主页 > 网页制作 > HTTP/TCP >

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

来源:互联网 收集:自由互联 发布时间:2021-06-16
地址:https://www.luogu.org/problem/P3370 求不同字符串的数量 这题用set也可以过,但是hash更高大上嘛。 哈希其实就是将一个字符串映射成一个值,并且要让这些值不能大概率地重复 进制哈希

地址:https://www.luogu.org/problem/P3370

求不同字符串的数量  

    这题用set也可以过,但是hash更高大上嘛。

    哈希其实就是将一个字符串映射成一个值,并且要让这些值不能大概率地重复

    进制哈希:进制哈希的核心便是给出一个固定进制base,将一个串的每一个元素看做一个进制位上的数字,所以这个串就可以看做一个base进制的数,这个数即为哈希值,

    本题通过一个固定的转换方式,使不同字符串的哈希值尽量不同。要避免哈希冲突,选取适当的进制,一般是选择大于所有字符对应的数字的最大值,然后mod一个很大的素数,最后判重就可以了。

    

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const int maxn=1e4+19;
const ll base=129;  
const long long mod=212370440130137957ll;  //我也不知道为啥用这个,记住就行了
ll has[maxn];
char s[maxn];
int ac(char *s)
{
    int len=strlen(s);
    ll sum=0;
    for(int i=0;i<len;i++)
    {
        sum=(sum*base+(ll)s[i])%mod;
    }
    return sum;
}
int main()
{
    ll t;
    scanf("%lld",&t);
    for(int i=0;i<t;i++)
    {
        scanf("%s",s);
        has[i]=ac(s);
    }
    sort(has,has+t);
    ll cnt=1;
    for(int i=0;i<t-1;i++)
    {
                if(has[i]!=has[i+1])
                cnt++;
    }
    printf("%lld\n",cnt);
    return 0;
} 
网友评论