字符串hash 洛谷3370 比眉伴天荒 2021-10-23 21:38 269阅读 0赞 ### 题目描述 ### 如题,给定N个字符串(第i个字符串长度为Mi,字符串内包含数字、大小写字母,大小写敏感),请求出N个字符串中共有多少个不同的字符串。 \#友情提醒:如果真的想好好练习哈希的话,请自觉,否则请右转PJ试炼场:) ### 输入格式 ### 第一行包含一个整数N,为字符串的个数。 接下来N行每行包含一个字符串,为所提供的字符串。 ### 输出格式 ### 输出包含一行,包含一个整数,为不同的字符串个数。 ### 输入输出样例 ### **输入 \#1**复制 5 abc aaaa abc abcc 12345 **输出 \#1**复制 4 #include<bits/stdc++.h> using namespace std; typedef unsigned long long ll; const int M=1e5+50; char s[M]; ll a[M]; int base=233; int n; ll has(){ int len=strlen(s); ll ans=0; for(int i=0;i<len;i++) ans=(ans*base+(int)s[i]); return ans; } int main(){ scanf("%d",&n); for(int i=1;i<=n;i++){ scanf("%s",s); a[i]=has(); } sort(a+1,a+n+1); int k=1; for(int i=2;i<=n;i++)if(a[i]!=a[i-1])k++; cout<<k<<endl; return 0; }
还没有评论,来说两句吧...