luogu-B2118 验证子串

GESP三级练习，字符串练习（C++三级大纲中6号知识点，字符串），难度★★☆☆☆。

luogu-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

说明/提示

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

题目分析

解题思路

1. 题目要求判断一个字符串是否为另一个字符串的子串。

2. 解题思路分析：

   • 需要判断两个字符串之间的包含关系
   • 使用字符串的查找功能来检测子串
   • 分三种情况：
     • str1 是 str2 的子串
     • str2 是 str1 的子串
     • 两者都不是对方的子串

3. 具体实现：

   • 读入两个字符串 str1 和 str2
   • 使用 string.find() 函数检查子串关系：
     • 如果 str2.find(str1) 找到匹配，说明 str1 是 str2 的子串
     • 如果 str1.find(str2) 找到匹配，说明 str2 是 str1 的子串
     • 如果都没找到，说明不存在子串关系
   • 按照题目要求的格式输出结果

4. 复杂度分析：

   • 时间复杂度：$O(n \times m)$，其中 $n$ 和 $m$ 分别是两个字符串的长度
   • 空间复杂度：$O(1)$，只需要存储两个字符串

{% include custom/custom-post-content-inner.html %}

示例代码

#include <cstdio>
#include <iostream>
#include <string>

int main() {
    // 声明两个字符串变量用于存储输入
    std::string str1;
    std::string str2;
    // 使用getline读取两行输入，每行一个字符串
    std::getline(std::cin, str1);
    std::getline(std::cin, str2);
    // 检查str1是否包含str2
    if (str1.find(str2) != std::string::npos) {
        // 如果str2是str1的子串，按格式输出结果
        printf("%s is substring of %s", str2.c_str(), str1.c_str());
    } 
    // 检查str2是否包含str1
    else if (str2.find(str1) != std::string::npos) {
        // 如果str1是str2的子串，按格式输出结果
        printf("%s is substring of %s", str1.c_str(), str2.c_str());
    } 
    // 如果两个字符串都不是对方的子串
    else {
        std::cout << "No substring";
    }
    return 0;
}

{% include custom/custom-post-content-footer.md %}

所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code

“luogu-”系列题目可在 洛谷题库 在线评测。

“bcqm-”系列题目可在 编程启蒙题库 在线评测。

GESP/CSP 认证学习微信公众号