---

博客主页： [小ᶻ☡꙳ᵃⁱᵍᶜ꙳] 本文专栏: C++

---

---

---

💯前言

• 在编程竞赛中，字符串处理是一个经常出现且非常重要的主题。无论是子串匹配、字符串翻转还是查找模式，字符串问题都涉及到很多算法的运用和优化思路。今天，我们以一个经典的字符串题目为例，详细探讨如何验证两个字符串之间的子串关系。本文不仅会分析题目和给出的不同解法，还会介绍核心函数 strstr 的功能，并对代码进行优化和扩展，最终形成一个完整的学习框架。
  C++ 参考手册
  

---

---

💯题目概述

B2118 验证子串

题目描述

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

输入格式

两个字符串，每行一个字符串。

输出格式

• 如果第一个字符串是第二个字符串的子串，输出：

  (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。

---

💯解决方案分析

初步分析与思路

子串验证问题本质上是一个字符串匹配问题。对于两个字符串 $s_1$ 和 $s_2$：

1. 若 $s_1$ 是 $s_2$ 的子串，则 $s_1$ 在 $s_2$ 中出现，并且顺序保持一致。
2. 若 $s_2$ 是 $s_1$ 的子串，则 $s_2$ 在 $s_1$ 中出现，并且顺序保持一致。
3. 如果两者都不是对方的子串，则不存在子串关系。

题目限制了字符串的长度不超过 20，这意味着暴力解决方案的时间复杂度较低时仍可以接受。然而，为了提升效率与代码的可读性，我们可以借助 C++ 的内置字符串操作函数。

下面我们会分别解析两种做法：

1. 我的代码实现：基于字符逐个比较的实现。
2. 老师的代码实现：基于标准库 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;
}

实现逻辑与优缺点

优点：

1. 代码思路清晰，易于理解。
2. 通过双重循环，尝试逐个字符匹配，确保了每个字符都得到验证。

问题与改进：

1. 错误的逻辑：

   • 我统计了两个字符串中每个字符是否能在另一个字符串中找到，但这并不能验证子串的顺序关系。
   • 例如，对于输入：

     abc
     cab
     

     我的代码会误判 abc 是 cab 的子串，因为所有字符都能匹配，但实际顺序并不一致。

2. 效率较低：

   • 代码中使用了双重循环，导致时间复杂度为 $O(n^2)$。当字符串长度较小时，问题不大，但如果题目限制放宽，这种方法的效率会成为瓶颈。

3. 冗余的计数变量：

   • 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;
}

核心逻辑分析

1. strstr 函数的使用

   • 定义：

     const char* strstr(const char* str1, const char* str2);
     

     • strstr 用于查找字符串 str2 是否是字符串 str1 的子串。
     • 如果找到子串，返回指向 str1 中子串起始位置的指针。
     • 如果没有找到，返回 NULL。
   • 在本题中，分别使用：
     • strstr(s2, s1) 检查 $s_1$ 是否为 $s_2$ 的子串。
     • strstr(s1, s2) 检查 $s_2$ 是否为 $s_1$ 的子串。

2. 逻辑清晰且高效

   • 判断 $s_1$ 和 $s_2$ 的子串关系时，直接调用 strstr，避免了手动遍历字符。
   • 相比双重循环的暴力方法，strstr 内部可能采用优化的字符串匹配算法（如 KMP 算法），使时间复杂度接近 $O(n)$。

3. 简洁性与可读性

   • 整体代码逻辑简单明了，无需额外的计数或复杂的循环。
   • 代码长度短，功能却完整。

总结

老师的代码实现了简单、高效、可靠的子串验证，适合直接解决题目需求。

---

💯优化与扩展

优化输入处理

1. 防止输入溢出：
   当前代码中，输入字符串长度如果超过 N - 1（20），可能导致缓冲区溢出。
   可以使用 cin.getline 限制输入长度：

   cin.getline(s1, N);
   cin.getline(s2, N);
   

2. 空字符串处理：
   如果输入为空字符串，程序应该直接输出 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 函数的强大功能及其高效性。同时，通过比较不同实现方法，我们发现了代码优化的重要性和标准库的优势。在实际开发中，合理利用现有工具可以显著提高代码质量和开发效率。

希望本文能够帮助读者更好地理解字符串处理问题，提升编程能力！

---

---