csp信奥赛C++高频考点专项训练之字符串 --【字符串排序】：合并序列

csp信奥赛C高频考点专项训练之字符串 --【字符串排序】合并序列题目描述有N NN个单词和字符串T TT按字典序输出以字符串T TT为前缀的所有单词。输入格式输入文件第一行包含一个正整数N NN接下来N NN行每行一个单词长度不超过100 100100最后一行包含字符串T TT。输出格式按字典序升序输出答案。输入输出样例 1输入 16 na no ki ki ka ku k输出 1ka 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且所有字符均为小写字母。思路分析题目要求输出所有以给定字符串 ( T ) 为前缀的单词并按字典序升序排列。最直接的方法将所有单词读入数组。遍历每个单词检查其前len(T)个字符是否与T相等需先保证单词长度 ≥len(T)。将符合条件的单词存入另一个数组。对该数组进行排序默认字典序。依次输出。时间复杂度为O ( N ⋅ L M log ⁡ M ) O(N \cdot L M \log M)O(N⋅LMlogM)其中 ( N ) 为单词总数( L ) 为单词平均长度≤100( M ) 为符合条件单词数。空间复杂度 O(N)。对于N ≤ 100000 N \le 100000N≤100000的数据完全可行且代码实现简洁。代码实现#includebits/stdc.husingnamespacestd;intmain(){intn;cinn;// 读入单词个数vectorstringa(n);// 存储所有单词for(inti0;in;i)cina[i];// 读入每个单词string t;cint;// 读入前缀Tvectorstringb;// 存储符合前缀条件的单词for(string s:a){// 遍历每个单词if(s.size()t.size()s.compare(0,t.size(),t)0)// 检查是否以T开头b.push_back(s);// 是则加入答案集合}sort(b.begin(),b.end());// 按字典序升序排序for(string s:b)couts\n;// 输出结果return0;}功能分析输入处理先读入整数 ( N )接着读入 ( N ) 个单词存入vectorstring a最后读入前缀字符串t。前缀筛选遍历a中每个单词s若s长度不小于t且s的前t.size()个字符与t完全相同则将s加入结果容器b。排序输出对b调用sort进行字典序升序排序最后逐行输出。正确性保留了重复单词严格按字典序输出满足题目要求。效率单次比较仅需O ( L ) O(L)O(L)时间排序O ( M log ⁡ M ) O(M \log M)O(MlogM)。【完整系列请查看专栏】信奥赛C普及组CSP-J一等奖通关刷题题单及题解https://blog.csdn.net/weixin_66461496/category_12673810.html 点击跳转各种学习资料助力大家一站式学习和提升#includebits/stdc.husingnamespacestd;intmain(){cout########## 一站式掌握信奥赛知识! ##########;cout############# 冲刺信奥赛拿奖! #############;cout###### 课程购买后永久学习不受限制! ######;return0;}【秘籍汇总】完整csp信奥赛C学习资料1、csp/信奥赛C完整信奥赛系列课程永久学习https://edu.csdn.net/lecturer/7901 点击跳转2、CSP信奥赛C竞赛拿奖视频课https://edu.csdn.net/course/detail/40437 点击跳转https://edu.csdn.net/course/detail/41081 点击跳转3、csp信奥赛高频考点知识详解及案例实践CSP信奥赛C动态规划https://blog.csdn.net/weixin_66461496/category_13096895.html点击跳转CSP信奥赛C标准模板库STLhttps://blog.csdn.net/weixin_66461496/category_13108077.html 点击跳转信奥赛C提高组csp-s知识详解及案例实践https://blog.csdn.net/weixin_66461496/category_13113932.html 点击跳转4、csp信奥赛冲刺一等奖有效刷题题解信奥赛C普及组CSP-J一等奖通关刷题题单及题解https://blog.csdn.net/weixin_66461496/category_12673810.html 点击跳转信奥赛C提高组csp-j初赛复赛真题题解持续更新https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转信奥赛C提高组csp-s初赛复赛真题题解持续更新https://blog.csdn.net/weixin_66461496/category_13125089.html 点击跳转5、GESP C考级真题题解GESP(C 一级二级三级)真题题解持续更新https://blog.csdn.net/weixin_66461496/category_12858102.html 点击跳转GESP(C 四级五级六级)真题题解持续更新https://blog.csdn.net/weixin_66461496/category_12869848.html 点击跳转GESP(C 七级八级)真题题解持续更新https://blog.csdn.net/weixin_66461496/category_13117178.html 点击跳转· 文末祝福 ·#includebits/stdc.husingnamespacestd;intmain(){cout跟着王老师一起学习信奥赛C;cout 成就更好的自己 ;cout csp信奥赛一等奖属于你! ;return0;}