計算字串中恰好出現K次的長度為M的子字串的數量

在本文中，我們將深入研究電腦科學領域中一個獨特且令人著迷的問題 - 「計算字串中恰好出現 K 次的 M 長度子字串」。這類問題在程式設計競賽和麵試中經常遇到。在開始之前，讓我們先定義一下我們正在處理的內容 -

• 子字串− 在另一個字串中找到的連續序列。

• #M 長度− 我們感興趣的子字串的長度。

• #K 次− 子字串應在原始字串中出現的確切次數。

#演算法說明

為了解決這個問題，我們將利用雜湊映射（在 C 中也稱為無序映射）的強大功能。哈希映射允許我們以鍵值對的形式儲存數據，並為搜尋和插入操作提供恆定的時間複雜度，使其成為解決此類問題的絕佳工具。

計算字串中恰好出現 K 次的 M 長度子字串的演算法如下 -

• 初始化一個空的哈希映射。

• 迭代字串，建立所有可能的 M 長度子字串。

• 對於每個子字串，將其新增至雜湊映射中。如果它已經存在，則增加其計數。

• 計算完所有子字串後，迭代雜湊映射以查找恰好出現 K 次的所有子字串。

C 實作

這是上述演算法的 C 實作 -

範例

#include<bits/stdc++.h>
using namespace std;

int countSubstrings(string s, int M, int K) {
   unordered_map<string, int> count_map;
   int n = s.length();
   
   for (int i = 0; i <= n - M; i++) {
      string substring = s.substr(i, M);
      count_map[substring]++;
   }
   
   int count = 0;
   for (auto it : count_map) {
      if (it.second == K)
         count++;
   }

    return count;
}

int main() {
   string s = "abcabcabc";
   int M = 3;
   int K = 3;
   
   int result = countSubstrings(s, M, K);
   cout << "The number of M-length substrings occurring exactly K times is: " << result << endl;
   
   return 0;
}

輸出

The number of M-length substrings occurring exactly K times is: 1

在上面的程式碼中，countSubstrings函數會輸入字串s、子字串的長度M和出現的次數K作為參數。它初始化一個無序映射 count_map 來追蹤所有子字串及其出現次數。然後它迭代該字串以創建長度為 M 的所有可能的子字串，並且對於每個子字串，它都會增加映射中的計數。一旦計算完所有子字串，它就會迭代映射以計算恰好出現 K 次的所有子字串。

main函數是程式碼執行開始的地方。它初始化字串 s 以及 M 和 K 的值。然後呼叫 countSubstrings 函數並列印結果。

測試案例範例

讓我們考慮字串“abcabcabc”，其中 M=3 且 K=3。

這裡，M長度的子字串是“abc”，“bca”，“cab”，“abc”，“bca”，“cab”，“abc”。很明顯，子字串「abc」在字串中恰好出現了 3 次，因此程式的輸出將為 1。

這種解決問題的方法，我們使用雜湊映射來計算子字串，是計算機科學中時空權衡的一個很好的例子。當我們使用額外的空間來儲存子字串及其計數時，我們可以透過在恆定時間內計算出現次數來顯著降低問題的時間複雜度。

時間與空間複雜度

此演算法的時間複雜度為O(n)，其中n是字串的長度。這是因為我們只迭代字串一次來建立所有可能的 M 長度子字串。

由於雜湊映射的儲存需求，空間複雜度也是 O(n)，在最壞的情況下，每個子字串都是唯一的，導致映射中存在 n 個不同的條目。

結論

在本文中，我們研究了計算機科學中的一個常見問題 - 計算在字串中恰好出現 K 次的 M 長度子字串的數量。我們使用哈希映射在 C 中實現了一個高效的解決方案，它為我們提供了恆定時間的搜尋和插入操作。這個問題是如何結合使用資料結構和演算法來有效解決複雜問題的完美範例。

以上是計算字串中恰好出現K次的長度為M的子字串的數量的詳細內容。更多資訊請關注PHP中文網其他相關文章！