P3370 【模板】字符串哈希
2017-09-02
题目描述
如题，给定N个字符串（第i个字符串长度为Mi，字符串内包含数字、大小写字母，大小写敏感），请求出N个字符串中共有多少个不同的字符串。
输入输出格式
输入格式：
第一行包含一个整数N，为字符串的个数。
接下来N行每行包含一个字符串，为所提供的字符串。
输出格式：
输出包含一行，包含一个整数，为不同的字符串个数。
输入输出样例
INPUT_1 7 bjcxg bjbcxg yyzcxg bjxdxg xgxg xgxg xgml OUT_1 6 INPUT_2 3 ldaxc xchld djaxc OUT_2 3
时空限制：1000ms,128M
数据规模：
对于30%的数据：N<=10，Mi≈6，Mmax<=15;
对于70%的数据：N<=1000，Mi≈100，Mmax<=150
对于100%的数据：N<=10000，Mi≈1000，Mmax<=1500
哈希,把字符串通过某个变成大数字,保证相同的字符串产生的大数字不一样;然后pd是否相同
我用的双哈希,我才不信什么玄学单哈希能过
#include<iostream> #include<cstdio> #include<algorithm> #include<cstdlib> #include<cstring> #define ll long long using namespace std; struct saber{ ll x,y; }ck[10000+999]; char a[5000]; int n; const ll sen=131; const ll mod1=23333333333ll; const ll mod2=10000000007ll; ll hax1(char s[]){ ll ans=0;int len=strlen(s); for(int i=0;i<len;i++) ans=(ans*sen+(ll)s[i])%mod1; return ans%mod1; } ll hax2(char s[]){ ll ans=0;int len=strlen(s); for(int i=0;i<len;i++) ans=(ans*sen+(ll)s[i])%mod2; return ans%mod2; } bool sa(saber x,saber y){ if(x.x==x.y)return x.y<y.y; return x.x<y.x; } int main(){ cin>>n; for(int i=1;i<=n;i++){ cin>>a; ck[i].x=hax1(a); ck[i].y=hax2(a); } sort(ck+1,ck+1+n,sa); int re=0; for(int i=1;i<=n;i++){ if((ck[i].x!=ck[i-1].x)||(ck[i].y!=ck[i-1].y))re++;} cout<<re; return 0; }
by:s_a_b_e_r
自然溢出大法好（其实就是因为懒x
用unsigned long long存hash值，这样在超过2^64的时候会重新从0开始计数
就相当于自动%了一个2^64
偷懒专用w
（虽然可能会被卡，但是如果出题人很良心的话就没问题
//自然溢出 #include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define ull unsigned long long using namespace std; ull base=131,a[10009],ans=1; char s[1509]; ull hashs() { ull re=0; int len=strlen(s); for(int i=0;i<len;++i) re=re*base+(ull)s[i]; return re&0x7fffffff; } int main() { int n; cin>>n; for(int i=1;i<=n;++i) { memset(s,0,sizeof(s)); scanf("%s",s); a[i]=hashs(); } sort(a+1,a+n+1); for(int i=2;i<=n;++i) {if(a[i]!=a[i-1])++ans;} cout<<ans<<endl; return 0; }
by:wypx
冰精吃西瓜
冰精不吃西瓜
幽幽子吃西瓜
冰精想冻西瓜
西瓜西瓜
西瓜西瓜
西瓜没了
s:西瓜会被玩坏的x
w:你说的是那个在uuz肚子里的西瓜吗？
