Hash就是一个像函数一样的东西,你放进去一个值,它给你输出来一个值。输出的值就是Hash值。一般Hash值会比原来的值更好储存(更小)或比较。

那字符串Hash就非常好理解了。就是把字符串转换成一个整数的函数。而且要尽量做到使字符串对应唯一的Hash值。

#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 10005
#define ull unsigned long long
using namespace std;
struct hh{ull x,y;}ans[N];
char st[1550];
const ull base=131;
const ull Mod1=19260817;
const ull Mod2=19660813;
ull hash1(char st[])
{
	int l=strlen(st);
	ull ans=0;
	for (int i=0;i<l;i++)
	  ans=(ans*base+(ull)st[i])%Mod1;
	return ans;
}
ull hash2(char st[])
{
	int l=strlen(st);
	ull ans=0;
	for (int i=0;i<l;i++)
	  ans=(ans*base+(ull)st[i])%Mod2;
	return ans;
}
int cmp(hh a,hh b){if (a.x==b.x) return a.y<b.y;else return a.x<b.x;}
int main()
{
	int n,i;
	scanf("%d",&n);
	for (i=1;i<=n;i++)
	{
		scanf("%s",&st);
		ans[i].x=hash1(st);
		ans[i].y=hash2(st);
	}
	sort(ans+1,ans+n+1,cmp);
	int ll=1;
	for (i=2;i<=n;i++)
	  if (ans[i-1].x!=ans[i].x || ans[i-1].y!=ans[i].y)
	    ll++;
	printf("%d",ll);
}
#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 10005
#define ull unsigned long long
using namespace std;
char st[1550];
ull ans[N];
const ull base=131;
ull hashs(char st[])
{
    int l=strlen(st);
    ull ans=0;
    for (int i=0;i<l;i++)
      ans=ans*base+(ull)st[i];
    return ans&0x7fffffff;//这里是取正
}
int main()
{
    int n,i;
    scanf("%d",&n);
    for (i=1;i<=n;i++)
    {
        scanf("%s",&st);
        ans[i]=hashs(st);
    }
    sort(ans+1,ans+n+1);
    int ll=1;
    for (i=2;i<=n;i++)
      if (ans[i-1]!=ans[i])
        ll++;
    printf("%d",ll);
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注