在本文中，我們將深入研究計(jì)算機(jī)科學(xué)領(lǐng)域中一個(gè)獨(dú)特且令人著迷的問題 – “計(jì)算字符串中恰好出現(xiàn) K 次的 M 長(zhǎng)度子字符串”。這類問題在編程競(jìng)賽和面試中經(jīng)常遇到。在開始之前，讓我們定義一下我們正在處理的內(nèi)容 –
子字符串??在另一個(gè)字符串中找到的連續(xù)序列。
M 長(zhǎng)度??我們感興趣的子字符串的長(zhǎng)度。
K 次??子字符串應(yīng)在原始字符串中出現(xiàn)的確切次數(shù)。
算法說(shuō)明
為了解決這個(gè)問題，我們將利用哈希映射（在 C++ 中也稱為無(wú)序映射）的強(qiáng)大功能。哈希映射允許我們以鍵值對(duì)的形式存儲(chǔ)數(shù)據(jù)，并為搜索和插入操作提供恒定的時(shí)間復(fù)雜度，使其成為解決此類問題的絕佳工具。
計(jì)算字符串中恰好出現(xiàn) K 次的 M 長(zhǎng)度子串的算法如下 –
初始化一個(gè)空的哈希映射。
迭代字符串，創(chuàng)建所有可能的 M 長(zhǎng)度子字符串。
對(duì)于每個(gè)子字符串，將其添加到哈希映射中。如果它已經(jīng)存在，則增加其計(jì)數(shù)。
計(jì)算完所有子字符串后，迭代哈希映射以查找恰好出現(xiàn) K 次的所有子字符串。
C++ 實(shí)現(xiàn)
這是上述算法的 C++ 實(shí)現(xiàn) –
示例
#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;
}
登錄后復(fù)制
輸出
The number of M-length substrings occurring exactly K times is: 1
登錄后復(fù)制
在上面的代碼中，countSubstrings函數(shù)將輸入字符串s、子字符串的長(zhǎng)度M和出現(xiàn)的次數(shù)K作為參數(shù)。它初始化一個(gè)無(wú)序映射 count_map 來(lái)跟蹤所有子字符串及其出現(xiàn)次數(shù)。然后它迭代該字符串以創(chuàng)建長(zhǎng)度為 M 的所有可能的子字符串，并且對(duì)于每個(gè)子字符串，它都會(huì)增加映射中的計(jì)數(shù)。一旦計(jì)算完所有子字符串，它就會(huì)迭代映射以計(jì)算恰好出現(xiàn) K 次的所有子字符串。
main函數(shù)是代碼執(zhí)行開始的地方。它初始化字符串 s 以及 M 和 K 的值。然后調(diào)用 countSubstrings 函數(shù)并打印結(jié)果。
測(cè)試用例示例
讓我們考慮字符串“abcabcabc”，其中 M=3 且 K=3。
這里，M長(zhǎng)度的子串是“abc”，“bca”，“cab”，“abc”，“bca”，“cab”，“abc”。很明顯，子字符串“abc”在字符串中恰好出現(xiàn)了 3 次，因此程序的輸出將為 1。
這種解決問題的方法，我們使用哈希映射來(lái)計(jì)算子字符串，是計(jì)算機(jī)科學(xué)中時(shí)空權(quán)衡的一個(gè)很好的例子。當(dāng)我們使用額外的空間來(lái)存儲(chǔ)子字符串及其計(jì)數(shù)時(shí)，我們可以通過(guò)在恒定時(shí)間內(nèi)計(jì)算出現(xiàn)次數(shù)來(lái)顯著降低問題的時(shí)間復(fù)雜度。
時(shí)間和空間復(fù)雜度
該算法的時(shí)間復(fù)雜度為O(n)，其中n是字符串的長(zhǎng)度。這是因?yàn)槲覀冎坏址淮蝸?lái)創(chuàng)建所有可能的 M 長(zhǎng)度子字符串。
由于哈希映射的存儲(chǔ)要求，空間復(fù)雜度也是 O(n)，在最壞的情況下，每個(gè)子字符串都是唯一的，導(dǎo)致映射中存在 n 個(gè)不同的條目。
結(jié)論
在本文中，我們研究了計(jì)算機(jī)科學(xué)中的一個(gè)常見問題 – 計(jì)算在字符串中恰好出現(xiàn) K 次的 M 長(zhǎng)度子字符串的數(shù)量。我們使用哈希映射在 C++ 中實(shí)現(xiàn)了一個(gè)高效的解決方案，它為我們提供了恒定時(shí)間的搜索和插入操作。這個(gè)問題是如何結(jié)合使用數(shù)據(jù)結(jié)構(gòu)和算法來(lái)有效解決復(fù)雜問題的完美示例。
以上就是計(jì)算字符串中恰好出現(xiàn)K次的長(zhǎng)度為M的子串的數(shù)量的詳細(xì)內(nèi)容，更多請(qǐng)關(guān)注www.xfxf.net其它相關(guān)文章！
