统计给定字符串中子字符串 X 在子字符串 Y 每次出现之前出现的总次数


在这个问题中,我们需要在给定字符串中找到子字符串 Y 时,计算字符串 str 中子字符串 X 的总出现次数。我们可以持续统计子字符串 X 的出现次数,当我们得到子字符串 Y 时,就可以打印计数的值。

问题陈述 – 我们给定一个字符串 str、X 和 Y。字符串的长度分别为 N、A 和 B。我们需要计算给定字符串 str 中子字符串 X 在子字符串 Y 每次出现之前的总出现次数。

示例

输入str = "stuxystuxy"; X = "stu"; Y = "xy";

输出– 1 2

解释

在子字符串 Y 的第一次出现 (stuxy) 之前,子字符串 X 出现 1 次。

在子字符串 Y 的第二次出现 (stuxystuxy) 之前,子字符串 X 出现 2 次。

输入– str = ‘aaccddee’ X = ‘a’ Y = ‘e’

输出– 2 2

解释– 在第一个和第二个 ‘e’ 之前,‘a’ 出现了 2 次。

输入– str = ‘xyz’ X = ‘pq’ Y = ‘yz’

输出– 0

解释– 子字符串 ‘yz’ 在给定字符串中只出现一次,但 ‘pq’ 没有出现。所以,输出为 0。

方法 1

在这种方法中,如果我们在给定字符串中找到子字符串 X,我们将把计数的值增加 1。当我们在字符串中找到子字符串 Y 时,我们将打印计数的值以显示子字符串 X 在子字符串 Y 每次出现之前的出现次数。

算法

  • 定义变量 ‘cntx’ 并将其初始化为零。

  • 将 str、X 和 Y 字符串的长度存储到 len、A 和 B 变量中。

  • 使用 for 循环遍历字符串。

  • 如果我们从当前索引开始找到子字符串 X,则将 ‘cntx’ 的值增加 1。

  • 如果我们从当前索引开始找到子字符串 Y,则打印 ‘cntx’ 的值。

示例

Open Compiler
#include <bits/stdc++.h> using namespace std; // function to cntX the occurrences of substring X before every occurrence of substring Y in the given string void countOccurrences(string str, string X, string Y) { // to store occurrences of X int cntX = 0; // get the lengths of strings str, X and Y int len = str.length(); int A = X.length(); int B = Y.length(); // Traverse the string str for (int i = 0; i < len; i++) { // If the substring str[i, i+A-1] equals X, then increment cntX by 1. if (str.substr(i, A) == X) cntX++; // If the substring str[i, i+B-1] is equal to Y, then print cntX if (str.substr(i, B) == Y) cout << cntX << " "; } } int main() { string str = "stuxystuxy"; string X = "stu"; string Y = "xy"; countOccurrences(str, X, Y); return 0; }

输出

1 2

时间复杂度 – O(len*(A + B)),其中 len 是字符串 str 的长度。A 和 B 分别是子字符串 X 和 Y 的长度。

空间复杂度 – O(1),因为我们使用常量空间来计算子字符串 X 的出现次数。

在上面的代码中,当我们找到从第 i 个索引开始的子字符串 Y 时,我们打印 ‘cntx’ 的值。程序员可以创建一个数组,并在找到子字符串 Y 时将 ‘cntX’ 的值存储到数组中。之后,他们可以从函数中返回结果数组,因为在实时开发中,需要从函数中返回结果而不是打印。

更新于:2023年8月18日

浏览量 140

开启您的职业生涯

完成课程获得认证

开始学习
广告