計算字符串中恰好出現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 函數并打印結果。