【例题2】图书管理（信息学奥赛一本通- P1456）

图书管理是一件十分繁杂的工作，在一个图书馆中每天都会有许多新书加入。为了更方便的管理图书（以便于帮助想要借书的客人快速查找他们是否有他们所需要的书），我们需要设计一个图书查找系统。

该系统需要支持 2 种操作：

add(s) 表示新加入一本书名为 s 的图书。

find(s) 表示查询是否存在一本书名为 s 的图书。

第一行包括一个正整数 n，表示操作数。 以下 n 行，每行给出 2 种操作中的某一个指令条，指令格式为：

add s find s

在书名 s 与指令（add，find）之间有一个隔开，我们保证所有书名的长度都不超过 200。可以假设读入数据是准确无误的。

对于每个 find(s) 指令，我们必须对应的输出一行 yes 或 no，表示当前所查询的书是否存在于图书馆内。

注意：一开始时图书馆内是没有一本图书的。并且，对于相同字母不同大小写的书名，我们认为它们是不同的。

数据范围

n≤30000。

今天和大家分享一道经典的字符串查找题目——图书查找系统。

这道题表面上只是简单的“存书”和“找书”，但如果你只是无脑开一个大数组，每次find都把数组从头到尾扫一遍，遇到稍微严格一点的评测机绝对会被卡成超时。

在解决这道题的过程中，我展示了代码的三次“进化”，下面把整个思考过程、三版代码的演进以及避坑指南整理出来。

一、 题目分析

• 核心需求：实现两个操作：add（添加书名）和find（查找书名是否存在）。

• 数据范围：操作数N≤30000，书名长度≤200。大小写敏感，带空格。

• 痛点：如果用普通的string数组存储，每次find操作的最坏时间复杂度是O(K×L)（K为已存书的数量，L为字符串长度）。如果有一半是add一半是find，运算次数会飙升到 15000×15000×200，肯定会超时。我们需要一个近乎O(1)的快速查找方案。

二、 代码的进化过程

进化阶段一：普通数组+手写字符串哈希 (V1)

既然直接比较长字符串太慢，第一反应是把字符串压缩成数字。利用unsigned long long(ull) 自动溢出取模的特性，用131进制把长达200个字符的书名变成一个巨大的整数，存进数组里。

虽然比较数字比比较字符串快，但查找时依然需要写个for(int i=1; i<=cnt; i++)遍历数组。治标不治本，虽然这道题能提交通过，但最坏复杂度还是 O(N^2)，在边缘疯狂试探。

V1代码实现：

//数组+哈希 #include <iostream> #include <cstring> using namespace std; typedef unsigned long long ull; int n; string func;//代表是何种操作 ull ans1[30010];//记录每个添加的图书的哈希值 int cnt=0;//总共添加书籍数 int main(){ ios::sync_with_stdio(false); cin.tie(0); cin>>n; while(n--){ cin>>func; cin.get();//吃掉操作符后面的空格 //增加操作 if(func[0]=='a'){ cnt++; string s; getline(cin,s); //算出当前添加这本书的哈希值并存入数组ans1 for(int i=0;i<s.size();i++) ans1[cnt]=ans1[cnt]*131+s[i]; } else if(func[0]=='f'){ bool flag=0; string s; getline(cin,s); ull ans2=0; for(int i=0;i<s.size();i++) ans2=ans2*131+s[i]; //问题：依然需要从头到尾扫一遍数组 for(int i=1;i<=cnt;i++){ if(ans2==ans1[i]){ flag=1; cout<<"yes"<<"\n"; break; } } if(flag==0) cout<<"no"<<'\n'; } } return 0; }

进化阶段二：STL 哈希表 + 手写哈希 (V2)

既然瓶颈在“遍历查找”上，直接祭出O(1)查找神器：unordered_set。我们建一个unordered_set<ull>，每次add时，先手动把字符串用131进制算出哈希数字，丢进set里；find时也算出数字，直接调用.count()判断。

优势：速度直接起飞。时间复杂度被死死压在了O(N×L)。这也是在高级算法竞赛中，为了防止出题人针对STL底层哈希进行“卡常（构造哈希冲突数据）”的标准硬核写法。

V2代码实现：

//哈希表加哈希优化 //数组+哈希 #include <iostream> #include <cstring> #include <unordered_set>//哈希表 using namespace std; typedef unsigned long long ull; int n; unordered_set<ull> ans3;//存放已有的图书的哈希值的哈希表 string func;//代表是何种操作 int main(){ ios::sync_with_stdio(false); cin.tie(0); cin>>n; while(n--){ cin>>func; cin.get();//吃掉操作符后面的空格 //增加操作 if(func[0]=='a'){ cnt++; string s; getline(cin,s); ull ans1=0;//临时变量 存储这一次添加的书名的哈希值 for(int i=0;i<s.size();i++) ans1=ans1*131+s[i]; ans3.insert(ans1); } else if(func[0]=='f'){ string s; getline(cin,s); ull ans2=0;//临时变量 存储这一次要查询的书名的哈希值 for(int i=0;i<s.size();i++) ans2=ans2*131+s[i]; //如果ans2当前已经存在哈希表中 输出yes if(ans3.count(ans2)) cout<<"yes"<<"\n"; //不存在 输出no else cout<<"no"<<"\n"; } } return 0; }

进化阶段三：纯血STL原生哈希 (V3)

写完 V2 后转念一想，这题毕竟是个纯应用题。C++的unordered_set底层其实自带了工业级的字符串哈希函数（如 MurmurHash或FNV-1a）。 既然标准库自己能搞定，而且分布极度均匀，干嘛还要苦哈哈地写for循环去乘131呢？直接把容器类型改成unordered_set<string>，把字符串原封不动地丢进去就行了。但是比赛还是不建议这么写，竞赛时容易针对哈希表自带字符串哈希函数构造测试点从而卡掉你

优势：代码极短，心智负担几乎为零，是最标准的工程开发写法。

V3代码实现：

//使用哈希表自带的字符串哈希函数 //不建议这么写，还是建议自己写哈希函数，因为竞赛时容易针对 //哈希表自带字符串哈希函数构造测试点从而卡掉你 //哈希表加哈希优化 //数组+哈希 #include <iostream> #include <cstring> #include <unordered_set>//哈希表 直接存字符串 自动算哈希 using namespace std; int n; unordered_set<string> ans;//存放已有的图书的哈希值的哈希表 string func;//代表是何种操作 int main(){ ios::sync_with_stdio(false); cin.tie(0); cin>>n; while(n--){ cin>>func; cin.get();//吃掉操作符后面的空格 //增加操作 if(func[0]=='a'){ string s; getline(cin,s);//读取带有空格的整行书名 ans.insert(s); } else if(func[0]=='f'){ string s; getline(cin,s); //如果字符串s当前已经存在哈希表中 输出yes if(ans.count(s)) cout<<"yes"<<"\n"; //不存在 输出no else cout<<"no"<<"\n"; } } return 0; }

三、易错点点总结

这道题逻辑虽然简单，但藏着几个极其容易白给的C++语法天坑：

1. 极其致命的“流冲突”与残留空格题目输入格式是add 书名。必然会用到cin>>func;，接着用getline(cin,s);。大坑：cin>>不会吃掉它读完后面的那个空格/换行符。如果不做处理，getline会直接把空格读进去，导致后续所有书名前面都多了一个空格，永远匹配不上。解法：在两者之间，必须加一个cin.get()，精准备用地吃掉分隔符。

2. ios::sync_with_stdio(false)的反噬加了流加速后，千万不要用C语言的getchar()去吃空格。因为C和C++的流已经解绑了，混用会导致读入彻底错乱。老老实实用C++的cin.get()。

3. 未初始化的局部变量在V1和V2中手动算哈希时，如果在while内部写ull ans2;而不赋初值，它会被分配一个内存残留的随机垃圾值。拿着垃圾值去乘131，算出来的哈希全错。一定要写ull ans2 = 0;。

写在最后：从手算131进制加数组遍历，到巧妙借用STLunordered_set，虽然代码行数变少了，但对底层内存排布、时间复杂度的认知要求却在逐步加深。能熟练把玩哈希表，基本上就拿到了字符串查重问题的万能钥匙。