【C++】B2118 验证子串
【C++】B2118 验证子串
💯前言
- 在编程竞赛中，字符串处理是一个经常出现且非常重要的主题。无论是子串匹配、字符串翻转还是查找模式，字符串问题都涉及到很多算法的运用和优化思路。今天，我们以一个经典的字符串题目为例，详细探讨如何验证两个字符串之间的子串关系。本文不仅会分析题目和给出的不同解法，还会介绍核心函数
strstr的功能，并对代码进行优化和扩展，最终形成一个完整的学习框架。 C++ 参考手册
💯题目概述
题目描述
输入两个字符串，验证其中一个字符串是否为另一个字符串的子串。
输入格式
两个字符串，每行一个字符串。
输出格式
如果第一个字符串是第二个字符串的子串，输出：
(s1) is substring of (s2)如果第二个字符串是第一个字符串的子串，输出：
(s2) is substring of (s1)如果两者都不是对方的子串，输出：
No substring输入输出样例
样例 1
输入：
abc
dddncabca输出：
abc is substring of dddncabca样例 2
输入：
aaa
bbb输出：
No substring题目提示
对于 100% 的数据，字符串长度不会超过 20。
💯解决方案分析
初步分析与思路
子串验证问题本质上是一个字符串匹配问题。对于两个字符串
和
：
- 若
是
的子串，则
在
中出现，并且顺序保持一致。
- 若
是
的子串，则
在
中出现，并且顺序保持一致。
- 如果两者都不是对方的子串，则不存在子串关系。
题目限制了字符串的长度不超过 20，这意味着暴力解决方案的时间复杂度较低时仍可以接受。然而，为了提升效率与代码的可读性，我们可以借助 C++ 的内置字符串操作函数。
下面我们会分别解析两种做法：
- 我的代码实现：基于字符逐个比较的实现。
- 老师的代码实现：基于标准库
strstr函数的实现。
同时，我们会对代码进行优化和扩展，探讨更通用的处理方法。
💯我的代码实现与分析
代码回顾
我的代码如下：
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int N = 25;
char ch1[N];
char ch2[N];
int main()
{
cin >> ch1;
cin >> ch2;
int len1 = strlen(ch1);
int len2 = strlen(ch2);
int i = 0, j = 0, count1 = 0, count2 = 0;
for (i = 0; i < len1; i++) {
for (j = 0; j < len2; j++) {
if (ch1[i] == ch2[j]) {
count1++;
break;
}
}
}
for (i = 0; i < len2; i++) {
for (j = 0; j < len1; j++) {
if (ch2[i] == ch1[j]) {
count2++;
break;
}
}
}
if (count1 == len1) {
cout << ch1 << " is substring of " << ch2 << endl;
} else if (count2 == len2) {
cout << ch2 << " is substring of " << ch1 << endl;
} else {
cout << "No substring" << endl;
}
return 0;
}
实现逻辑与优缺点
优点：
- 代码思路清晰，易于理解。
- 通过双重循环，尝试逐个字符匹配，确保了每个字符都得到验证。
问题与改进：
错误的逻辑：
我统计了两个字符串中每个字符是否能在另一个字符串中找到，但这并不能验证子串的顺序关系。
例如，对于输入：
abc
cab
我的代码会误判 abc 是 cab 的子串，因为所有字符都能匹配，但实际顺序并不一致。
效率较低：
- 代码中使用了双重循环，导致时间复杂度为
。当字符串长度较小时，问题不大，但如果题目限制放宽，这种方法的效率会成为瓶颈。
冗余的计数变量：
count1和count2的逻辑本质上与判断子串无关，可以省略。
总结
虽然我的代码在小范围数据下可以完成任务，但存在逻辑漏洞，且效率和可读性都可以进一步优化。
💯老师的代码实现与分析
代码回顾
以下是老师的代码：
#include <iostream>
#include <cstring>
using namespace std;
const int N = 20;
char s1[N];
char s2[N];
int main() {
cin >> s1;
cin >> s2;
if (strstr(s2, s1))
cout << s1 << " is substring of " << s2 << endl;
else if (strstr(s1, s2))
cout << s2 << " is substring of " << s1 << endl;
else
cout << "No substring" << endl;
return 0;
}
核心逻辑分析
strstr 函数的使用
定义：
const char* strstr(const char* str1, const char* str2);strstr用于查找字符串str2是否是字符串str1的子串。- 如果找到子串，返回指向
str1中子串起始位置的指针。 - 如果没有找到，返回
NULL。
在本题中，分别使用：
strstr(s2, s1)检查
是否为
的子串。
strstr(s1, s2)检查
是否为
的子串。
逻辑清晰且高效
- 判断
和
的子串关系时，直接调用 strstr，避免了手动遍历字符。
- 相比双重循环的暴力方法，
strstr内部可能采用优化的字符串匹配算法（如 KMP 算法），使时间复杂度接近
。
简洁性与可读性
- 整体代码逻辑简单明了，无需额外的计数或复杂的循环。
- 代码长度短，功能却完整。
总结
老师的代码实现了简单、高效、可靠的子串验证，适合直接解决题目需求。
💯优化与扩展
优化输入处理
防止输入溢出：
当前代码中，输入字符串长度如果超过 N - 1（20），可能导致缓冲区溢出。
可以使用 cin.getline 限制输入长度：
cin.getline(s1, N);
cin.getline(s2, N);空字符串处理：
如果输入为空字符串，程序应该直接输出 No substring，而不是调用 strstr。
if (strlen(s1) == 0 || strlen(s2) == 0) {
cout << "No substring" << endl;
return 0;
}扩展功能：查找子串位置
如果需要输出子串的位置，可以通过 strstr 的返回值计算：
const char* result = strstr(s2, s1);
if (result) {
cout << s1 << " is substring of " << s2 << " at position " << (result - s2) << endl;
}💯小结
通过对本题的解析，我们不仅学习了子串验证的基本方法，还深入了解了 strstr 函数的强大功能及其高效性。同时，通过比较不同实现方法，我们发现了代码优化的重要性和标准库的优势。在实际开发中，合理利用现有工具可以显著提高代码质量和开发效率。
希望本文能够帮助读者更好地理解字符串处理问题，提升编程能力！
腾讯云开发者
