题解 2366: 信息学奥赛一本通T1456-图书管理

解题思路:主要要用hash表，把单个字符映射一个数字的方式，比如说字符串abAB01就可以映射为{97,98,65,66,48,49}。希望把这串序列成0，mod-1中的一个数字

称为字符串的hash值，转换方式和k进制转换十进制一样，就是不停的迭代运算hash=(hash*k+s[i])%mod即可，k的值也可以任意选，但是一般来说不少于128（ascill字符集的数量）,当然，求hash的方法不唯一，例如如果字符集局限于a到z的小写字母，也可以吧每个字母映射0到25，此时基数为26.

这里的mod会取一个一个比较大的质数以便减少冲突的可能性，而且在空间允许的情况下尽可能大，例如10007,999983等，根据情况选。由于可能有多个不同的字符串对应同一个hash值，对每个hash值建立一个vector（或者链表都可以），这样就可以将这个插入的字符串和其相同的所有字符串比较，看看是否相等，就知道这个字符串是否出现过。
注意事项:

参考代码:

#include  <iostream>
#include <vector>//可变长度线性表的头文件

using namespace std;

char s[15500];//这个数组还是开大点，不然过不了

vector <string> sz[23335];//创建可变二维字符串类型数组

int n;

inline void add()
{

int hash=1;


for(int i=0;s[i];i++)
{

if(s[i]==' ') continue;//遇到空格，就继续找下一个字符，


hash=(hash *111* 261 + s[i])%23333;//计算出字符串的hash的值

}

string t = s;

for(int i=0;i<sz[hash].size();i++)//遍历hash值为当前字符串hash值的hash链表,以检查这个字符串是否已经存在


if(sz[hash][i]==t) return;//存在直接返回


sz[hash].push_back(t);//不存在将字符串hash值放入

}

inline void find()
{

int hash=1;

for(int i=0;s[i];i++)
{

if(s[i]==' ') continue;

hash=(hash *111* 261 + s[i])%23333;//计算出字符串的hash的值

}

string t = s;


for(int i=0;i<sz[hash].size();i++)//遍历hash值为当前字符串hash值的hash链表,以检查这个字符串是否已经存在

if(sz[hash][i]==t) 
{

cout<<"yes"<<endl;//存在就返回yes

return;

}

cout<<"no"<<endl;
}
int main()
{
cin>>n;

for(int i=1;i<=n;i++)
{
string text;

cin>>text;

if(text=="add")//添加
{

gets(s);//要用gets()因为要输入空格（名字里有空格）

add();

}

else if(text=="find")//查询
{

gets(s);//要用gets()因为要输入空格（名字里有空格）


find();

}

}

return 0;

}