本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。欢迎大家订阅我的专栏算法题解C与Python实现附上汇总贴算法竞赛备考冲刺必刷题C | 汇总【题目来源】洛谷P2908 [USACO08OPEN] Word Power S - 洛谷【题目描述】约翰想要计算他那N ( l ≤ N ≤ 1000 ) N(l \le N \le 1000)N(l≤N≤1000)只奶牛的名字的能量。每只奶牛的名字由不超过1000 10001000个字符构成没有一个名字是空字符串。约翰有一张“能量字符串表”上面有M ( 1 ≤ M ≤ 100 ) M(1 \le M \le 100)M(1≤M≤100)个代表能量的字符串。每个字符串由不超过30 3030个字符构成同样不存在空字符串。一个奶牛的名字蕴含多少个能量字符串这个名字就有多少能量。所谓“蕴含”是指某个能量字符串的所有字符都在名字串中按顺序出现不一定一个紧接着一个。所有的大写字母和小写字母都是等价的。比如在贝茜的名字Bessie里蕴含有Be、si、EE、Es等等字符串但不蕴含Ls或eB。请帮约翰计算他的奶牛的名字的能量。【输入】第一行两个正整数N , M N,MN,M。下面N NN行每行一个字符串代表一只奶牛的名字。下面M MM行每行一个字符串代表一个能量字符串。【输出】对每个名字输出一行一个整数表示其能量值。【输入样例】5 3 Bessie Jonathan Montgomery Alicia Angola se nGo Ont【输出样例】1 1 2 0 1【核心思想】问题分析给定N NN个奶牛名字和M MM个能量字符串判断每个名字蕴含多少个能量字符串。蕴含指能量字符串的所有字符在名字中按顺序出现不必连续且大小写不敏感。这是一个字符串子序列匹配问题关键在于对每个名字-能量串对进行按顺序的字符查找。算法选择统一转小写预处理将所有名字和能量字符串转为小写消除大小写差异顺序查找匹配对每个能量字符串的每个字符在名字中从上次找到位置的下一个位置开始查找验证是否为子序列关键步骤读取输入N , M N, MN,MN NN个名字M MM个能量字符串预处理将所有字符串转为小写tolower逐个判断对每个名字n a m e [ i ] name[i]name[i]初始化c n t 0 cnt 0cnt0遍历每个能量字符串p o w e r [ j ] power[j]power[j]p o s 0 pos 0pos0m a r k 0 mark 0mark0遍历p o w e r [ j ] power[j]power[j]的每个字符c cc在n a m e [ i ] name[i]name[i]中从p o s pospos开始查找c cc若找到p o s 找到位置 1 pos \text{找到位置} 1pos找到位置1若未找到m a r k 1 mark 1mark1跳出若m a r k 0 mark 0mark0c n t 1 cnt \mathrel{} 1cnt1输出c n t cntcnt时间/空间复杂度时间复杂度O ( N ⋅ M ⋅ L name ⋅ L power ) O(N \cdot M \cdot L_{\text{name}} \cdot L_{\text{power}})O(N⋅M⋅Lname​⋅Lpower​)最坏情况下对每个字符都执行一次find空间复杂度O ( N ⋅ L name M ⋅ L power ) O(N \cdot L_{\text{name}} M \cdot L_{\text{power}})O(N⋅Lname​M⋅Lpower​)存储字符串子序列匹配的核心思想顺序性约束能量字符串的字符必须在名字中保持相对顺序通过维护p o s pospos指针确保每次查找在上次位置之后大小写无关统一转小写后比较避免复杂的分支判断线性扫描string::find从指定位置开始线性扫描最坏O ( L name ) O(L_{\text{name}})O(Lname​)但由于L name ≤ 1000 L_{\text{name}} \le 1000Lname​≤1000且L power ≤ 30 L_{\text{power}} \le 30Lpower​≤30实际效率可接受适用于子序列判定 大小写不敏感类问题核心是顺序查找和位置维护【解题思路】【算法标签】#普及- #字符串入门【代码详解】#includebits/stdc.husingnamespacestd;intn,m;string name[1005];string power[105];intmain(){cinnm;// 输入n和mfor(inti1;in;i){// 输入n个name需要将其统一转为小写字符串cinname[i];for(intj0;jname[i].length();j){name[i][j]tolower(name[i][j]);}}for(inti1;im;i){// 输入m个能量字符串也需要将其转为小写字符串cinpower[i];for(intj0;jpower[i].length();j){power[i][j]tolower(power[i][j]);}}for(inti1;in;i){// 遍历n个name字符串intcnt0;// 统计蕴含多少能量字符串初始化为0for(intj1;jm;j){// 遍历m个能量字符串intmark0;// 定义标记位intpos0;// 定义字符串的查找起始位置初始为0for(intk0;kpower[j].length();k){// 遍历每个能量字符串的所有字符if(name[i].find(power[j][k],pos)0name[i].find(power[j][k],pos)name[i].length()){// 如果在name[i]的长度范围内能找到posname[i].find(power[j][k],pos)1;// 更新pos为找到位置的下一个位置}else{mark1;// 否则修改markbreak;// 并退出循环}}if(mark0)cnt;// 如果k次循环结束后mark仍为0说明所有字符都可以找到cnt自增1}coutcntendl;// 输出结果}return0;}【运行结果】5 3 Bessie Jonathan Montgomery Alicia Angola se nGo Ont 1 1 2 0 1