csp信奥赛C++标准模板库STL案例应用8
csp信奥赛C++标准模板库STL案例应用8
multiset实践
题目描述
有N NN个单词和字符串T TT，按字典序输出以字符串T TT为前缀的所有单词。
输入格式
输入文件第一行包含一个正整数N NN；
接下来N NN行，每行一个单词，长度不超过100 100100；
最后一行包含字符串T TT。
输出格式
按字典序升序输出答案。
输入输出样例 1
输入 1
6 na no ki ki ka ku k输出 1
ka ki ki ku说明/提示
【数据规模】
对于60 % 60\%60%的数据，满足1 ≤ N ≤ 1000 1 \le N \le 10001≤N≤1000；
对于100 % 100\%100%的数据，满足1 ≤ N ≤ 100000 1 \le N \le 1000001≤N≤100000且所有字符均为小写字母。
算法思路分析
这个代码实现了一个查找具有指定前缀的所有单词并按字典序输出的功能。主要思路如下：
核心算法
- 使用 multiset 存储单词：multiset 会自动按字典序排序，且允许重复元素
- 前缀匹配：遍历排序后的单词，检查每个单词是否以目标前缀开头
- 输出结果：符合条件的所有单词按顺序输出
时间复杂度分析
- 插入 N 个单词到 multiset：O(N log N)
- 遍历所有单词：O(N)
- 每个单词的前缀比较：O(|T|)，其中 |T| 是前缀长度
- 总时间复杂度：O(N log N + N × |T|)
空间复杂度分析
- multiset 存储所有单词：O(N × L)，其中 L 是平均单词长度
代码实现
#include<bits/stdc++.h>usingnamespacestd;intn;// 单词数量multiset<string>ms;// 使用multiset存储单词（自动排序且允许重复）intmain(){// 读取单词数量cin>>n;// 读取所有单词并插入multisetfor(inti=1;i<=n;i++){string s;cin>>s;ms.insert(s);// multiset会自动按字典序排序}// 读取目标前缀string t;cin>>t;// 遍历所有单词（此时已按字典序排序）for(autow:ms){// 使用compare函数检查前缀匹配：// w.compare(0, t.length(), t) 比较w从位置0开始、长度为t.length()的子串是否等于t// 如果相等，返回0if(w.compare(0,t.length(),t)==0){cout<<w<<endl;// 输出匹配的单词}}return0;}功能分析
优势
- 简洁高效：利用 multiset 的自动排序特性，无需手动排序
- 正确处理重复单词：multiset 允许重复，符合题目要求
- 前缀匹配准确：使用
compare()函数精确比较前缀
测试用例分析
对于样例输入：
6 na no ki ki ka ku k- multiset 按字典序存储：{“ka”, “ki”, “ki”, “ku”, “na”, “no”}
- 前缀 “k” 匹配的单词：“ka”, “ki”, “ki”, “ku”
- 输出顺序正确且保持了原单词的出现顺序（对于相同单词 “ki” 出现两次）
适用场景
- 适合处理中等规模的数据（N ≤ 100,000）
- 需要按字典序输出结果
- 单词长度相对较短（≤100）
各种学习资料，助力大家一站式学习和提升！！！
#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"########## 一站式掌握信奥赛知识! ##########";cout<<"############# 冲刺信奥赛拿奖! #############";cout<<"###### 课程购买后永久学习，不受限制! ######";return0;}- 一、CSP信奥赛C++通关学习视频课：
- C++语法基础
- C++语法进阶
- C++算法
- C++数据结构
- CSP信奥赛数学
- CSP信奥赛STL
- 二、CSP信奥赛C++竞赛拿奖视频课：
- 信奥赛csp-j初赛高频考点解析
- CSP信奥赛C++复赛集训课（12大高频考点专题集训）
- 三、考级、竞赛刷题题单及题解：
- GESP C++考级真题题解
- CSP信奥赛C++初赛及复赛高频考点真题解析
- CSP信奥赛C++一等奖通关刷题题单及题解
详细内容：
1、csp/信奥赛C++，完整信奥赛系列课程（永久学习）：
https://edu.csdn.net/lecturer/7901 点击跳转
2、CSP信奥赛C++竞赛拿奖视频课：
https://edu.csdn.net/course/detail/40437 点击跳转
3、csp信奥赛冲刺一等奖有效刷题题解：
CSP信奥赛C++初赛及复赛高频考点真题解析（持续更新）：https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转
- 2025 csp-j 复赛真题及答案解析（最新更新）
- 2025 csp-x(山东) 复赛真题及答案解析（最新更新）
- 2025 csp-x(河南) 复赛真题及答案解析（最新更新）
- 2025 csp-x(辽宁) 复赛真题及答案解析（最新更新）
- 2025 csp-x(江西) 复赛真题及答案解析（最新更新）
- 2025 csp-x(广西) 复赛真题及答案解析（最新更新）
- 2020 ~ 2024 csp 复赛真题题单及题解
- 2019 ~ 2022 csp-j 初赛高频考点真题分类解析
- 2021 ~ 2024 csp-s 初赛高频考点解析
- 2023 ~ 2024 csp-x (山东)初赛真题及答案解析
- 2024 csp-j 初赛真题及答案解析
- 2025 csp-j 初赛真题及答案解析（最新更新）
- 2025 csp-s 初赛真题及答案解析（最新更新）
- 2025 csp-x (山东)初赛真题及答案解析(最新更新)
- 2025 csp-x (江西)初赛真题及答案解析(最新更新)
- 2025 csp-x (辽宁)初赛真题及答案解析(最新更新)
CSP信奥赛C++一等奖通关刷题题单及题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12673810.html 点击跳转
- 129 道刷题练习和详细题解，涉及：模拟算法、数学思维、二分算法、 前缀和、差分、深搜、广搜、DP专题、 树和图
4、GESP C++考级真题题解：
GESP(C++ 一级+二级+三级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12858102.html 点击跳转
GESP(C++ 四级+五级+六级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12869848.html 点击跳转
· 文末祝福 ·
#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"跟着王老师一起学习信奥赛C++";cout<<" 成就更好的自己！ ";cout<<" csp信奥赛一等奖属于你! ";return0;}