【模板】字符串哈希

题目描述

如题，给定N个字符串（第i个字符串长度为Mi，字符串内包含数字、大小写字母，大小写敏感），请求出N个字符串中共有多少个不同的字符串。

输入输出格式

输入格式：

第一行包含一个整数N，为字符串的个数。

接下来N行每行包含一个字符串，为所提供的字符串。

输出格式：

输出包含一行，包含一个整数，为不同的字符串个数

数据规模：

对于30%的数据：N<=10，Mi≈6，Mmax<=15;

对于70%的数据：N<=1000，Mi≈100，Mmax<=150

对于100%的数据：N<=10000，Mi≈1000，Mmax<=1500

以前一直没写过啊

说一下吧

直接把字符串S搞成一个P进制数，选择一个大小比要求放进去的字符串个数平方稍大的模数作为剩余系，然后排序去重即可

Code:

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define ll long long
const ll mod=1e9+7;
const ll base=233;
ll Map[10010];
ll Hash(char c[])
{
    int len=strlen(c);
    ll d=0,f=base;
    for(int i=0;i<len;i++)
    {
        (d+=c[i]*f)%=mod;
        (f*=base)%=mod;
    }
    return d;
}
int main()
{
    int n;
    char c[1502];
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%s",c);
        Map[i]=Hash(c);
    }
    sort(Map+1,Map+1+n);
    printf("%d
",unique(Map+1,Map+1+n)-Map-1);
    return 0;
}

2018.8.18 UPDATA

CH1401 兔子与兔子 0x10

描述

很久很久以前，森林里住着一群兔子。有一天，兔子们想要研究自己的 DNA 序列。我们首先选取一个好长好长的 DNA 序列（小兔子是外星生物，DNA 序列可能包含 26 个小写英文字母），然后我们每次选择两个区间，询问如果用两个区间里的 DNA 序列分别生产出来两只兔子，这两个兔子是否一模一样。注意两个兔子一模一样只可能是他们的 DNA 序列一模一样。

输入格式

第一行一个 DNA 字符串 S。
接下来一个数字 m，表示 m 次询问。
接下来 m 行，每行四个数字 l1, r1, l2, r2，分别表示此次询问的两个区间，注意字符串的位置从1开始编号。
其中 1 ≤ length(S), m ≤ 1000000

输出格式

对于每次询问，输出一行表示结果。如果两只兔子完全相同输出 Yes，否则输出 No（注意大小写

Code：

#include <cstdio>
#include <cstring>
#define ll long long
const int N=1e6+10;
const ll base=26;
const ll mod=1e9+7;
ll has[N],pow[N];
int m;
char s[N];
ll get_hash(int l,int r)
{
    return ((has[r]-has[l-1]*pow[r+1-l]%mod)%mod+mod)%mod;
}
int main()
{
    scanf("%s%d",s+1,&m);
    int n=strlen(s+1);
    pow[0]=1;
    for(int i=1;i<=n;i++)
    {
        has[i]=(has[i-1]*base+s[i]-'a')%mod;
        pow[i]=pow[i-1]*base%mod;
    }
    for(int l1,r1,l2,r2,i=1;i<=m;i++)
    {
        scanf("%d%d%d%d",&l1,&r1,&l2,&r2);
        if(get_hash(l1,r1)==get_hash(l2,r2)) printf("Yes
");
        else printf("No
");
    }
    return 0;
}

2018.7.23

【模板】 字符串哈希