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

【题目描述】图书管理是一件十分繁杂的工作在一个图书馆中每天都会有许多新书加入。为了更方便的管理图书以便于帮助想要借书的客人快速查找他们是否有他们所需要的书我们需要设计一个图书查找系统。该系统需要支持 2 种操作add(s) 表示新加入一本书名为 s 的图书。find(s) 表示查询是否存在一本书名为 s 的图书。【输入】第一行包括一个正整数 n表示操作数。 以下 n 行每行给出 2 种操作中的某一个指令条指令格式为add s find s在书名 s 与指令addfind之间有一个隔开我们保证所有书名的长度都不超过 200。可以假设读入数据是准确无误的。【输出】对于每个 find(s) 指令我们必须对应的输出一行 yes 或 no表示当前所查询的书是否存在于图书馆内。注意一开始时图书馆内是没有一本图书的。并且对于相同字母不同大小写的书名我们认为它们是不同的。【输入样例】4 add Inside C# find Effective Java add Effective Java find Effective Java【输出样例】no yes【提示】数据范围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 i1; icnt; 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 cnt0;//总共添加书籍数 int main(){ ios::sync_with_stdio(false); cin.tie(0); cinn; while(n--){ cinfunc; cin.get();//吃掉操作符后面的空格 //增加操作 if(func[0]a){ cnt; string s; getline(cin,s); //算出当前添加这本书的哈希值并存入数组ans1 for(int i0;is.size();i) ans1[cnt]ans1[cnt]*131s[i]; } else if(func[0]f){ bool flag0; string s; getline(cin,s); ull ans20; for(int i0;is.size();i) ans2ans2*131s[i]; //问题依然需要从头到尾扫一遍数组 for(int i1;icnt;i){ if(ans2ans1[i]){ flag1; coutyes\n; break; } } if(flag0) coutno\n; } } return 0; }进化阶段二STL 哈希表 手写哈希 (V2)既然瓶颈在“遍历查找”上直接祭出O(1)查找神器unordered_set。我们建一个unordered_setull每次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_setull ans3;//存放已有的图书的哈希值的哈希表 string func;//代表是何种操作 int main(){ ios::sync_with_stdio(false); cin.tie(0); cinn; while(n--){ cinfunc; cin.get();//吃掉操作符后面的空格 //增加操作 if(func[0]a){ cnt; string s; getline(cin,s); ull ans10;//临时变量 存储这一次添加的书名的哈希值 for(int i0;is.size();i) ans1ans1*131s[i]; ans3.insert(ans1); } else if(func[0]f){ string s; getline(cin,s); ull ans20;//临时变量 存储这一次要查询的书名的哈希值 for(int i0;is.size();i) ans2ans2*131s[i]; //如果ans2当前已经存在哈希表中 输出yes if(ans3.count(ans2)) coutyes\n; //不存在 输出no else coutno\n; } } return 0; }进化阶段三纯血STL原生哈希 (V3)写完 V2 后转念一想这题毕竟是个纯应用题。C的unordered_set底层其实自带了工业级的字符串哈希函数如 MurmurHash或FNV-1a。 既然标准库自己能搞定而且分布极度均匀干嘛还要苦哈哈地写for循环去乘131呢直接把容器类型改成unordered_setstring把字符串原封不动地丢进去就行了。但是比赛还是不建议这么写竞赛时容易针对哈希表自带字符串哈希函数构造测试点从而卡掉你优势代码极短心智负担几乎为零是最标准的工程开发写法。V3代码实现//使用哈希表自带的字符串哈希函数 //不建议这么写还是建议自己写哈希函数因为竞赛时容易针对 //哈希表自带字符串哈希函数构造测试点从而卡掉你 //哈希表加哈希优化 //数组哈希 #include iostream #include cstring #include unordered_set//哈希表 直接存字符串 自动算哈希 using namespace std; int n; unordered_setstring ans;//存放已有的图书的哈希值的哈希表 string func;//代表是何种操作 int main(){ ios::sync_with_stdio(false); cin.tie(0); cinn; while(n--){ cinfunc; 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)) coutyes\n; //不存在 输出no else coutno\n; } } return 0; }三、易错点点总结这道题逻辑虽然简单但藏着几个极其容易白给的C语法天坑极其致命的“流冲突”与残留空格题目输入格式是add 书名。必然会用到cinfunc;接着用getline(cin,s);。大坑cin不会吃掉它读完后面的那个空格/换行符。如果不做处理getline会直接把空格读进去导致后续所有书名前面都多了一个空格永远匹配不上。解法在两者之间必须加一个cin.get()精准备用地吃掉分隔符。ios::sync_with_stdio(false)的反噬加了流加速后千万不要用C语言的getchar()去吃空格。因为C和C的流已经解绑了混用会导致读入彻底错乱。老老实实用C的cin.get()。未初始化的局部变量在V1和V2中手动算哈希时如果在while内部写ull ans2;而不赋初值它会被分配一个内存残留的随机垃圾值。拿着垃圾值去乘131算出来的哈希全错。一定要写ull ans2 0;。写在最后从手算131进制加数组遍历到巧妙借用STLunordered_set虽然代码行数变少了但对底层内存排布、时间复杂度的认知要求却在逐步加深。能熟练把玩哈希表基本上就拿到了字符串查重问题的万能钥匙。