統計給定字串中子字串 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’ 的值儲存到陣列中。之後，他們可以從函式中返回結果陣列，因為在即時開發中，需要從函式中返回結果而不是列印。