[特殊字符] 2025蓝桥杯备赛Day8—

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

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

🚀 题目速览

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

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

B2118 验证子串

题目描述

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

输入格式

两行，每行一个字符串。

输出格式

若第一个串 $s_1$ 是第二个串 $s_2$ 的子串，则输出(s1) is substring of (s2)；

否则，若第二个串 $s_2$ 是第一个串 $s_1$ 的子串，输出(s2) is substring of (s1)；

否则，输出 No substring。

输入输出样例 #1

输入 #1

abc
dddncabca

输出 #1

abc is substring of dddncabca

输入输出样例 #2

输入 #2

aaa
bbb

输出 #2

No substring

说明/提示

对于 $\%$ 的数据，字符串长度在 $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`	后判断成立