字符串哈希小结

输入格式 Input Format
	输入的第一行是一个整数N（1 <= N <= 50000），表示这个学期有多少天,也就是有多少人来请教。接下来的N行中，每行包含一个字符串，第i行表示第i位请教的人的名字,名字的长度小于201,且只包含小写字母.


	输出格式 Output Format
		输出包括若干行，如果第i位请教者已经请教过了,那么就输出I,所有输出必须从小到大。即顺序输出所有HZGD不用回答请教者的时候.

大概这样不用复制全部题目也能看懂吧,xxoj的p1337-请教[虽然这是蓝的,但是显而易见这不是个链接]

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 using namespace std;
 6 const int su=524287;
 7 int n;
 8 int tail=0;
 9 int hash[su+30];
10 char cha[205];
11 char aaa[100003][205];
12 /*
13 哈希表构建方式:加一位乘一个素数mod一个素数,用两个数组,哈希表(int)相应位置记录信息位置,用另一个数组(char二维)记录储存的名字.
14 */
15 inline int myfind(char *ch){//①
16     int num=0,ck;
17     int ll=strlen(ch);//②
18     for(int i=0;i<ll;i++){
19         num=(num*137+ch[i])%su;//神奇的137
20     }
21     while(hash[num]){
22         ck=strcmp(aaa[hash[num]],ch);//③
23         if(ck==0){
24             return 1;
25         }
26         else{
27             num=(num+1)%su ;
28         }
29     }
30     strcpy(aaa[++tail],ch);//④
31     hash[num]=tail;
32     return 0;
33 }
34 int main(){
35     scanf("%d
",&n);
36     bool wtf=1;
37     for(int i=1;i<=n;i++){
38         gets(cha);   
39         if(myfind(cha)){
40             cout<<i<<endl;
41             wtf=0;
42         }
43     }
44     if(wtf){
45         cout<<0<<endl;
46     }
47     return 0;
48 }

View Code

不负责任丢代码[大多数是参(chao)考(xi)大牛的]

1 int makehash(char *str) //BKDR hash
2 {
3     unsigned int seed = (MMM & 0x7FFFFFFF);
4     unsigned int hash = 0;//这里用了无符号的整数，所以不会出现负数
5     while (*str)
6 hash = hash * seed + (*str++);
7     return (hash & 0x7FFFFFFF);
8 }

View Code

//另一种字符串哈希函数

https://www.byvoid.com/blog/string-hash-compare

大牛金光闪闪的字符串hash详解↑

OJ练习题：

P1335

P1336

P1337

P1199

上面一段都是我从nyx学长的ppt里复制粘贴下来的,大概具体的还要复习一下课件

嗯从上面的程序可以看出,写这个东西需要用到char*和很多str函数(cstring)

1.char*:char型指针,未知大小,可以指向char数组,可用sizeof(),strlen()取长度;[http://www.jb51.net/article/55157.htm具体分析]

2.strlen():计算给定字符串长度 http://baike.baidu.com/item/strlen/2737

3.strcmp():原型声明:de >externde> de >intde> de >strcmpde>de >(de>de >constde> de >charde> de >*s1,de>de >constde> de >charde> de >*s2);de>比较两个字符串 (

设这两个字符串为str1，str2;若str1==str2，则返回零；

若str1<str2，则返回负数；

若str1>str2，则返回正数。) http://baike.baidu.com/item/strcmp

4.strcpy():原型声明：char *strcpy(char* dest, const char *src);功能：把从src地址开始且含有NULL结束符的字符串复制到以dest开始的地址空间.

就是把一个字符串里的东西全都放到另一个字符串里,

做成链接太麻烦了剩下的直接自己搜百科好了....

嗯其他str函数http://blog.csdn.net/kangroger/article/details/24383571