🔍 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;
}
📚 知识点总结
一、关键库函数
-
string::find()
size_t pos = s.find(sub); // 返回sub首次出现的位置 // 返回值说明： // - 找到：返回合法索引（0 ≤ pos < s.size()） // - 未找到：返回string::npos（通常为-1）
二、暴力匹配算法
-
双循环结构
for (主串遍历) {for (子串遍历) {逐字符比对} } -
时间复杂度：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(n⋅m)（暴力匹配，实际效率低） |
| 扩展性 | 高：仅需修改哈希表键值对即可支持新规则 | 低：需修改多个条件分支，易引入逻辑错误 |
| 可读性 | ★★★★★：规则集中可视化，逻辑清晰 | ★★★☆☆：分支嵌套复杂时需逐行推导逻辑 |
| 内存占用 | 约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）
👉 思考题：若要求判断是否是连续子序列（可不连续），如何修改代码？
答案提示：需使用双指针法遍历两个字符串。
