資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究統計字串中出現恰好 K 次的 M 長度子字串
在本文中，我們將深入探討計算機科學領域一個獨特而有趣的問題——“統計字串中出現恰好 K 次的 M 長度子字串”。這類問題在程式設計競賽和麵試中經常遇到。在開始之前，讓我們先定義一下我們要處理的內容：
子字串 − 在另一個字串中找到的連續序列。
M 長度 − 我們感興趣的子字串的長度。
K 次 − 子字串在原始字串中出現的精確次數。
演算法解釋
為了解決這個問題，我們將利用雜湊對映（在 C++ 中也稱為無序對映）的功能。雜湊對映允許我們將資料儲存在鍵值對中，併為搜尋和插入操作提供常數時間複雜度，這使得它們成為解決此類問題的絕佳工具。
統計字串中出現恰好 K 次的 M 長度子字串的演算法如下：
初始化一個空的雜湊對映。
遍歷字串，建立所有可能的 M 長度子字串。
對於每個子字串，將其新增到雜湊對映中。如果它已經存在，則遞增其計數。
在所有子字串都被計數之後，遍歷雜湊對映以查詢所有出現恰好 K 次的子字串。
C++ 實現
以下是上述演算法的 C++ 實現：
示例
以下是實現上述演算法的程式：
#include <stdio.h>
#include <string.h>
int countSubstrings(char *s, int M, int K) {
char substr[M + 1]; // Array to hold the current substring
int n = strlen(s); // Length of the input string
int count = 0; // Variable to store the count of valid substrings
// Loop through the string to find substrings
for (int i = 0; i <= n - M; i++) {
strncpy(substr, s + i, M); // Copy M characters from the current position
substr[M] = '\0'; // Null-terminate the substring
int freq = 1; // Initialize frequency of the current substring
// Count the frequency of the current substring in the rest of the string
for (int j = i + 1; j <= n - M; j++) {
if (strncmp(substr, s + j, M) == 0) {
freq++;
}
}
if (freq == K) {
count++; // Increment count if frequency matches K
}
}
return count;
}
int main() {
char s[] = "abcabcabc";
int M = 3;
int K = 3;
int result = countSubstrings(s, M, K);
printf("The number of M length substring occurring exactly K times is: %d\n", result);
return 0;
}
輸出
The number of M-length substrings occurring exactly K times is: 1
#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
import java.util.HashMap;
import java.util.Map;
public class Main {
public static int countSubstrings(String s, int M, int K) {
Map<String, Integer> countMap = new HashMap<>(); // Map to store substring frequencies
int n = s.length(); // Length of the input string
// Loop through the string to find substrings
for (int i = 0; i <= n - M; i++) {
String substring = s.substring(i, i + M); // Extract the current substring
countMap.put(substring, countMap.getOrDefault(substring, 0) + 1); // Update substring frequency
}
int count = 0;
// Count the substrings with frequency equal to K
for (int freq : countMap.values()) {
if (freq == K) {
count++;
}
}
return count;
}
public static void main(String[] args) {
String s = "abcabcabc";
int M = 3;
int K = 3;
int result = countSubstrings(s, M, K);
System.out.println("The number of M length substring occurring exactly K times is: " + result);
}
}
輸出
The number of M-length substrings occurring exactly K times is: 1
def count_substrings(s, M, K):
count_map = {} # Dictionary to store substring frequencies
n = len(s) # Length of the input string
# Loop through the string to find substrings
for i in range(n - M + 1):
substring = s[i:i+M] # Extract the current substring
if substring in count_map:
count_map[substring] += 1
else:
count_map[substring] = 1
count = 0
# Count the substrings with frequency equal to K
for freq in count_map.values():
if freq == K:
count += 1
return count
def main():
s = "abcabcabc"
M = 3
K = 3
result = count_substrings(s, M, K)
print("The number of M length substring occurring exactly K times is:", result)
if __name__ == "__main__":
main()
輸出
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++ 中實現了一個有效的解決方案，它為我們提供了常數時間的搜尋和插入操作。這個問題是資料結構和演算法如何結合起來有效地解決複雜問題的完美示例。
368 次瀏覽
