http://acm.uestc.edu.cn/#/problem/show/1092
韩爷的梦
Time Limit: 200/100MS (Java/Others) Memory Limit: 1300/1300KB (Java/Others)
一天，韩爷去百度面试，面试官给了他这么一个问题。
给你2万个字符串，每个字符串长度都是100，然后把2万个字符串丢入一个 set< string >g 中，问最终set里含有多少个元素？
g 是一个用来存储字符串、具有去重功能的容器，即相同字符串在 g 中只能保留一个。
两个字符串相等，当且仅当，长度一样且对应位置的字符都一样。
韩爷前晚没睡好，随手写了一个程序交给面试官，然后就gg了。
#include<iostream>
#include<string>
#include<set>
using namespace std;
string s;
set<string>g;
int main(){
for(int k=1;k<=20000;k++){
cin>>s;
g.insert(s);
}
cout<<g.size()<<endl;
return 0;
}
韩爷醒来之后，发现这只是一个梦（还好只是个梦）。他回忆起梦中的面试官给他的内存限制和时间限制非常低，这么做肯定过不了，那么，现在你不在梦中，你能解决这个问题么？
Input
单case
每个case有且只有2万行，每一行包含一个字符串，每行字符串的长度都为100 （样例除外）
字符集：大写英文字母（A－Z），小写英文字母（a－z），数字（0－9）
Output
输出一个整数，表示最终set里含有多少个元素。
Sample input and output
| Sample Input | Sample Output |
|---|---|
aaAa |
4 |
Hint
样例只是样例，不在test中
注意时间限制和内存限制非常低
思路：这道题目难点在于时间与内存限制很苛刻，一般的方法不能奏效，这里只能采用hash。即把每个字符串hash为一个数字，对数字进行比对，题目就ac了。还有个问题就是，hash函数的选取。我第一次选的hash函数就产生了冲突，这个可以多次选择进行测试，也可以直接采用更复杂的hash函数。我偷懒了下，选的是前者的方法，第二发就ac了。
这里说下关于hash的知识：
求一个字符串的hash值：
假设我们取p=13 ，mod=101
先把abc映射为一个整数
hash[0]=1，表示 a 映射为1
hash[1]=(hash[0]*p+idx(b))%mod=15，表示 ab 映射为 15
hash[2]=(hash[1]*p+idx(c))%mod=97
这样，我们就把 abc 映射为 97 这个数字了。
hash值呢？
unsigned long long hash[N];
定义一个unsigned long long类型的变量，它的范围是在[0, 2^64) 内，这就相当于，当数超不过2^64-1后，它会溢出！这就相当于一个数模2^64的过程。
那么hash函数可以理解为：
hash[i]=(hash[i-1]*p)%(2^64)
P取一个大素数，一般习惯取1e9+7或1e9+9
安全指数：三星（所以并不是很安全）
这个之前已经提到过了。
hash[i]=(hash[i-1]*p+idx(s[i]))%mod
hash1[i]=(hash1[i-1]*p+idx(s[i]))%mod1
hash2[i]=(hash2[i-1]*p+idx(s[i]))%mod2
pair<hash1,hash2>表示一个字符串！
解释：
hash1[i]=(hash1[i-1]*p+idx(s[i]))%mod1
hash2[i]=(hash2[i-1]*p+idx(s[i]))%mod2
mod1一般取1e9+7，mod2一般取1e9+9为什么这么取？
1000000007和1000000009是一对孪生素数，取它们，冲突的概率极低！
但请注意，hash的维度越高，耗时越高，耗内存越大！一般情况下，single hash可以被hack掉，但double hash极难被hack掉， 用double hash足以解决问题
ok，现在上这道题目的ac代码：
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <string>
#include <set>
using namespace std; #define MAX 0x7fffffff
#define N 20000
#define len 100 const unsigned long long p=1e9+;
const unsigned long long mod=1e9+; unsigned long long sv[N]; unsigned long long hashStr(char *s); int main(){
//freopen("D:\\input.in","r",stdin);
//freopen("D:\\output.out","w",stdout);
char tmp[];
for(int i=;i<N;i++){
gets(tmp);
sv[i]=hashStr(tmp);
}
sort(sv,sv+N);
int ans=,cu=-;
for(int i=;i<N;i++){
if(sv[i]!=cu){
cu=sv[i];
ans++;
}
}
printf("%d\n",ans);
return ;
}
unsigned long long hashStr(char *s){
unsigned long long h=;
for(int i=;i<len;i++){
unsigned long long value;
char c=s[i];
if(c>=''&&c<='') value=c-'';
else if(c>='a'&&c<='z') value=c-'a'+;
else value=c-'A'+;
h=(h*p+value)%mod;
}
return h;
}