计算字符串中恰好出现K次的长度为M的子串的数量

在本文中，我们将深入研究计算机科学领域中一个独特且令人着迷的问题 - “计算字符串中恰好出现 K 次的 M 长度子字符串”。这类问题在编程竞赛和面试中经常遇到。在开始之前，让我们定义一下我们正在处理的内容 -

• 子字符串− 在另一个字符串中找到的连续序列。

• M 长度− 我们感兴趣的子字符串的长度。

• K 次− 子字符串应在原始字符串中出现的确切次数。

算法说明

为了解决这个问题，我们将利用哈希映射（在 C++ 中也称为无序映射）的强大功能。哈希映射允许我们以键值对的形式存储数据，并为搜索和插入操作提供恒定的时间复杂度，使其成为解决此类问题的绝佳工具。

计算字符串中恰好出现 K 次的 M 长度子串的算法如下 -

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

• 迭代字符串，创建所有可能的 M 长度子字符串。

• 对于每个子字符串，将其添加到哈希映射中。如果它已经存在，则增加其计数。

• 计算完所有子字符串后，迭代哈希映射以查找恰好出现 K 次的所有子字符串。

  

  Sora

  Sora是OpenAI发布的一种文生视频AI大模型，可以根据文本指令创建现实和富有想象力的场景。

  下载

C++ 实现

这是上述算法的 C++ 实现 -

示例

#include
using namespace std;

int countSubstrings(string s, int M, int K) {
   unordered_map 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++ 中实现了一个高效的解决方案，它为我们提供了恒定时间的搜索和插入操作。这个问题是如何结合使用数据结构和算法来有效解决复杂问题的完美示例。