欢迎来到尧图网

客户服务 关于我们

您的位置:首页 > 房产 > 建筑 > [特殊字符] 2025蓝桥杯备赛Day8——B2118 验证子串

[特殊字符] 2025蓝桥杯备赛Day8——B2118 验证子串

2025/3/22 8:44:00 来源:https://blog.csdn.net/m0_74849460/article/details/146427852  浏览:    关键词:[特殊字符] 2025蓝桥杯备赛Day8——B2118 验证子串

🔍 2025蓝桥杯备赛Day8——B2118 验证子串

🚀 题目速览

题目难度:⭐️ 适合掌握字符串基本操作

考察重点:子串判断、字符串查找、条件分支处理

B2118 验证子串

题目描述

输入两个字符串,验证其中一个串是否为另一个串的子串。

输入格式

两行,每行一个字符串。

输出格式

若第一个串 s 1 s_1 s1 是第二个串 s 2 s_2 s2 的子串,则输出(s1) is substring of (s2)

否则,若第二个串 s 2 s_2 s2 是第一个串 s 1 s_1 s1 的子串,输出(s2) is substring of (s1)

否则,输出 No substring

输入输出样例 #1

输入 #1

abc
dddncabca

输出 #1

abc is substring of dddncabca

输入输出样例 #2

输入 #2

aaa
bbb

输出 #2

No substring

说明/提示

对于 100 % 100 \% 100% 的数据,字符串长度在 20 20 20 以内。

🔥 解法一:直接查找法(推荐)

🛠️ 实现思路

核心技巧:利用 string::find 函数进行子串判断

算法优势:代码简洁,时间复杂度 O(n*m)(n和m为字符串长度)

#include <iostream>
#include <string>
using namespace std;int main() {string s1, s2;getline(cin, s1);  // 读取第一个字符串(兼容含空格输入)getline(cin, s2);  // 读取第二个字符串// 核心判断逻辑(利用string::find)if (s2.find(s1) != string::npos) {  // 判断s1是否在s2中cout << s1 << " is substring of " << s2 << endl;} else if (s1.find(s2) != string::npos) {  // 判断s2是否在s1中cout << s2 << " is substring of " << s1 << endl;} else {cout << "No substring" << endl;  // 无包含关系}return 0;
}

🔥 解法二:双检暴力匹配法

🛠️ 实现思路

核心技巧:手动实现子串匹配逻辑,加深算法理解

教学价值:理解字符串匹配底层原理

#include <iostream>
#include <string>
using namespace std;// 自定义子串判断函数(暴力匹配)
bool isSubstring(const string& mainStr, const string& subStr) {if (subStr.empty()) return true;  // 空串是任意字符串的子串if (mainStr.size() < subStr.size()) return false;  // 主串更短时直接返回// 双重循环逐字符匹配for (int i = 0; i <= mainStr.size() - subStr.size(); ++i) {  // 主串起始位置遍历bool match = true;for (int j = 0; j < subStr.size(); ++j) {  // 子串逐字符比对if (mainStr[i + j] != subStr[j]) {  // 发现不匹配字符match = false;break;  // 提前结束内层循环}}if (match) return true;  // 完全匹配时返回成功}return false;  // 遍历结束未找到匹配
}int main() {string s1, s2;getline(cin, s1);getline(cin, s2);// 分支判断逻辑if (isSubstring(s2, s1)) {  // 先判断s1是否是s2的子串cout << s1 << " is substring of " << s2 << endl;} else if (isSubstring(s1, s2)) {  // 再判断s2是否是s1的子串cout << s2 << " is substring of " << s1 << endl;} else {cout << "No substring" << endl;  // 双重判断失败}return 0;
}

📚 知识点总结

一、关键库函数

  1. string::find()

    size_t pos = s.find(sub); // 返回sub首次出现的位置
    // 返回值说明:
    // - 找到:返回合法索引(0 ≤ pos < s.size())
    // - 未找到:返回string::npos(通常为-1)
    

二、暴力匹配算法

  1. 双循环结构

    for (主串遍历) {for (子串遍历) {逐字符比对}
    }
    
  2. 时间复杂度:O(n*m)(最坏情况)

三、string::npos 深度解析

特性说明
定义static const size_t npos = -1,本质是size_t类型的最大值(64位系统为18446744073709551615
用途表示字符串查找失败(如find()未匹配到子串),或表示“直到字符串末尾”的截取操作(如substr(pos, npos)
使用规范必须与size_t类型变量比较,避免与int混用导致的逻辑错误
典型错误if (s.find("x") == -1)(错误,应写为if (s.find("x") == string::npos)

🔥 双解法对比分析

维度直接查找法(解法一)双检暴力匹配法(解法二)
时间复杂度O(1)(哈希表查询)O(nm)(暴力匹配,实际效率低)
扩展性:仅需修改哈希表键值对即可支持新规则:需修改多个条件分支,易引入逻辑错误
可读性★★★★★:规则集中可视化,逻辑清晰★★★☆☆:分支嵌套复杂时需逐行推导逻辑
内存占用约30字节(存储哈希表)0额外内存:无数据结构存储开销
抗错能力:自动处理所有合法输入,未匹配时返回npos:依赖首字母正确性,非法输入易导致错误

🚨 常见错误警示

错误1:输入顺序颠倒

// 错误:先判断s1是否在s2中,但变量顺序颠倒
if (s1.find(s2) != npos) { ... } 
// 正确顺序应保持题目要求的判断顺序

错误2:空字符串处理

// 错误:未处理空字符串导致逻辑异常
if (s2.find(s1) != npos) // 若s1为空则恒成立
// 修正:题目保证输入非空(根据样例)

错误3:输出格式错误

// 错误:变量输出顺序颠倒
cout << s2 << "..." << s1; // 与题意要求不符

🌟 举一反三

变种题1:统计子串出现次数

int count = 0;
size_t pos = 0;
while ((pos = s.find(sub, pos)) != string::npos) {++count;pos += sub.size(); // 非重叠统计
}

变种题2:大小写不敏感判断

// 将字符串统一转为小写再比较
string lower_str = str;
transform(lower_str.begin(), lower_str.end(), lower_str.begin(), ::tolower);

🛠️ 实战技巧

1. 输入优化

// 使用快速IO(关闭同步流)
ios::sync_with_stdio(false);
cin.tie(nullptr);

2. 边界测试用例

测试案例预期输出测试目的
s1=“a”, s2=“a”a is substring of a完全相同字符串
s1=“ab”, s2=“abc”ab is substring of abc前部匹配
s1=“abc”, s2=“aababc”abc is substring of aababc后部匹配
s1=“abcd”, s2=“abc”abc is substring of abcd后判断成立

蓝桥杯考场策略

  • 优先使用解法一:代码简洁,不易出错
  • 注意输出格式:严格按照题目要求的字符串顺序输出
  • 极端情况测试:测试长度相差悬殊的字符串(如s1长度20,s2长度1)

👉 思考题:若要求判断是否是连续子序列(可不连续),如何修改代码?

答案提示:需使用双指针法遍历两个字符串。

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

热搜词