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

WBOY 转载: 2023-09-20 18:17:06 464浏览

在本文中，我们将深入研究计算机科学领域中一个独特且令人着迷的问题 - “计算字符串中恰好出现 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 函数并打印结果。