算法练习题04：连续子字符串出现的次数

题目描述

在2021年11月6日，中国战队EDG（Edward Gaming）在冰岛雷克雅未克举行的《英雄联盟》全球总决赛中，击败了韩国战队DK（DWG KIA），首次捧起召唤师杯。

虽然两支队伍在比赛中表现都很出色，但DK在比赛前期似乎拥有优势。他们在进入半决赛之前未曾输掉一局，并且是唯一一支以全胜战绩从小组赛出线的队伍。然而，EDG最终在决赛中击败了DK，赢得了总冠军。

为庆祝这次伟大的胜利，你写了一段长长的字符串，其中包含了“edgnb”这个子字符串。现在，你需要编写一个程序，统计字符串中“edgnb”出现的次数。

输入描述

输入为一个包含小写拉丁字母（即a到z）的非空字符串，字符串的长度不超过200,000个字符。

输出描述

输出一个整数，表示字符串中“edgnb”作为连续子字符串出现的次数。

示例

输入：

edgnb

输出： 

1

Java AC答案

import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);String text = scanner.nextLine();String aimStr = "edgnb";int count = count(aimStr, text);System.out.println(count);}public static int count(String aimStr, String str) {int count = 0;int index = 0;while ((index = str.indexOf(aimStr, index)) != -1) {count++;index++;  // 只移动一位，检查是否有重叠的子串}return count;}
}

C++ AC答案

#include <bits/stdc++.h>
using namespace std;
int main() {char str[200001];cin >> str;int count = 0;int index = 0;int len = strlen(str);  // 获取输入字符串的长度while (index <= len - 5) {  // 确保检查到最后一个可能的子串位置if (str[index] == 'e' && str[index + 1] == 'd' && str[index + 2] == 'g' &&str[index + 3] == 'n' && str[index + 4] == 'b') {count++;}index++;  // 逐字符向后移动，检查是否存在重叠的子串}cout << count << endl;return 0;
}