题目链接
题意:
给定N个字符串(第i个字符串长度为Mi,字符串内包含数字、大小写字母,大小写敏感),请求出N个字符串中共有多少个不同的字符串。
单hash——模数19260817(80分)
#include
#include
#include
#include
using namespace std;
const long long base=233;
const long long mod=19260817;
char s[100005];
long long f[100005];
int n;
long long hash(char s[])
{
long long ans=0;
for(int i=0;i<strlen(s);i++)
{
ans=(ans*base+(long long)s[i])%mod;
}
return ans;
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%s",s);
f[i]=hash(s);
}
sort(f+1,f+n+1);
int ans=1;
for(int i=2;i<=n;i++)
{
if(f[i]!=f[i-1]) ans++;
}
cout<<ans<<endl;
}
单hash——模数202370440130137957(AC)
推荐使用这种做法,一是简洁好写,二是误差小,三是时间快(100ms)
#include
#include
#include
#include
using namespace std;
const long long base=233;
const long long mod=212370440130137957ll;
char s[100005];
long long f[100005];
int n;
long long hash(char s[])
{
long long ans=0;
for(int i=0;i<strlen(s);i++)
{
ans=(ans*base+(long long )s[i])%mod;
}
return ans;
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%s",s);
f[i]=hash(s);
}
sort(f+1,f+n+1);
int ans=1;
for(int i=2;i<=n;i++)
{
if(f[i]!=f[i-1]) ans++;
}
cout<<ans<<endl;
}
双hash——模数19260817、19660813(AC)
时间较慢,有可能卡掉
#include
#include
#include
#include
using namespace std;
const long long base=233;
const long long mod1=19260817;
const long long mod2=19660813;
char s[100005];
struct node
{
long long x,y;
}f[100005];
int n;
long long hash1(char s[])
{
long long ans=0;
for(int i=0;i<strlen(s);i++)
{
ans=(ans*base+(long long)s[i])%mod1;
}
return ans;
}
long long hash2(char s[])
{
long long ans=0;
for(int i=0;i<strlen(s);i++)
{
ans=(ans*base+(long long)s[i])%mod2;
}
return ans;
}
bool cmp1(node a,node b)
{
return a.x<b.x;
}
bool cmp2(node a,node b)
{
return a.y<b.y;
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%s",s);
f[i].x=hash1(s);
f[i].y=hash2(s);
}
sort(f+1,f+n+1,cmp1);
sort(f+1,f+n+1,cmp2);
int ans=1;
for(int i=2;i<=n;i++)
{
if(f[i].x!=f[i-1].x || f[i].y!=f[i-1].y) ans++;
}
cout<<ans<<endl;
}
建议上述long long转为unsigned long long,好处是定义为ull的数在超过2^32的时候会自然溢出