luogu-B3663 [语言月赛202209] Luogu Academic

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

luogu-B3663 [语言月赛202209] Luogu Academic

题目要求

题目描述

七海在 LA 群中游走，获得了一个由英文小写字符组成的字符串 $S$。

七海想要知道，子串 luogu 在其中出现了多少次。

提示： 一个字符串中，任意连续的字符构成的子字符串称为子串。

例如，字符串 abc 一共包含 7 个子串，分别为：空串（不包含任何字符)，a，ab，abc，b，bc，c。注意，字符串 ac 不是 abc 的子串。

输入格式

输入一行一个字符串 $S$。

输出格式

输出一行一个整数，代表子串 luogu 在字符串 $S$ 中出现的次数。

输入输出样例 #1

输入 #1

luoluoguluogu

输出 #1

2

说明/提示

对于 $30\%$ 的数据，$|S| < 5$；
对于另外 $30\%$ 的数据，字符串 $S$ 仅由以下四个字符 l,u,o,g 组成；
对于 $100\%$ 的数据，$1 \le |S| \le 10^6$，保证字符串仅由小写英文字母组成。

题目分析

解题思路

1. 读取一行字符串输入，存储到string变量中
2. 遍历字符串，查找"luogu"子串：
   • 使用循环遍历字符串的每个字符
   • 检查从当前位置开始的5个字符是否为"luogu"
3. 统计子串出现次数：
   • 如果找到"luogu"子串，计数器加1
   • 跳过已匹配的5个字符，继续查找
   • 如果不匹配，移动到下一个字符继续查找
4. 输出统计结果

复杂度分析：

• 时间复杂度为 $O(n)$，其中n为输入字符串的长度
• 空间复杂度为 $O(1)$，只需要常数级额外空间

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

示例代码

#include <iostream>
#include <string>

int main() {
    // 定义字符串变量存储输入
    std::string str;
    // 读取一行输入
    getline(std::cin, str);
    // 计数器，记录"luogu"出现的次数
    int count = 0;
    // 遍历字符串
    for (int i = 0; i < str.length(); ) {
        // 如果从当前位置开始的5个字符是"luogu"
        if (str.substr(i,5) == "luogu") {
            // 计数器加1
            count++;
            // 跳过这5个字符
            i += 5;
        } else {
            // 否则继续检查下一个字符
            i++;
        }
    }
    // 输出结果
    std::cout << count << std::endl;
    return 0;
}

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

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

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

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

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