统计给定字符串中子字符串 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’ 的值。

示例

#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’ 的值存储到数组中。之后，他们可以从函数中返回结果数组，因为在实时开发中，需要从函数中返回结果而不是打印。