搜索
首页后端开发C++计算字符串中恰好出现K次的长度为M的子串的数量

计算字符串中恰好出现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 函数并打印结果。

测试用例示例

让我们考虑字符串“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++ 中实现了一个高效的解决方案,它为我们提供了恒定时间的搜索和插入操作。这个问题是如何结合使用数据结构和算法来有效解决复杂问题的完美示例。

以上是计算字符串中恰好出现K次的长度为M的子串的数量的详细内容。更多信息请关注PHP中文网其他相关文章!

声明
本文转载于:tutorialspoint。如有侵权,请联系admin@php.cn删除
C面试问题和答案:ACE您的下一次技术评估C面试问题和答案:ACE您的下一次技术评估Apr 28, 2025 am 12:10 AM

C 面试中,智能指针是关键工具,帮助管理内存并减少内存泄漏。1)std::unique_ptr提供独占所有权,确保资源自动释放。2)std::shared_ptr用于共享所有权,适用于多引用场景。3)std::weak_ptr可避免循环引用,确保安全资源管理。

C的未来:改编和创新C的未来:改编和创新Apr 27, 2025 am 12:25 AM

C 的未来将专注于并行计算、安全性、模块化和AI/机器学习领域:1)并行计算将通过协程等特性得到增强;2)安全性将通过更严格的类型检查和内存管理机制提升;3)模块化将简化代码组织和编译;4)AI和机器学习将促使C 适应新需求,如数值计算和GPU编程支持。

C的寿命:检查其当前状态C的寿命:检查其当前状态Apr 26, 2025 am 12:02 AM

C 在现代编程中依然重要,因其高效、灵活和强大的特性。1)C 支持面向对象编程,适用于系统编程、游戏开发和嵌入式系统。2)多态性是C 的亮点,允许通过基类指针或引用调用派生类方法,增强代码的灵活性和可扩展性。

C#vs. C性能:基准测试和注意事项C#vs. C性能:基准测试和注意事项Apr 25, 2025 am 12:25 AM

C#和C 在性能上的差异主要体现在执行速度和资源管理上:1)C 在数值计算和字符串操作上通常表现更好,因为它更接近硬件,没有垃圾回收等额外开销;2)C#在多线程编程上更为简洁,但性能略逊于C ;3)选择哪种语言应根据项目需求和团队技术栈决定。

C:死亡还是简单地发展?C:死亡还是简单地发展?Apr 24, 2025 am 12:13 AM

1)c relevantduetoItsAverity and效率和效果临界。2)theLanguageIsconTinuellyUped,withc 20introducingFeaturesFeaturesLikeTuresLikeSlikeModeLeslikeMeSandIntIneStoImproutiMimproutimprouteverusabilityandperformance.3)

C在现代世界中:应用和行业C在现代世界中:应用和行业Apr 23, 2025 am 12:10 AM

C 在现代世界中的应用广泛且重要。1)在游戏开发中,C 因其高性能和多态性被广泛使用,如UnrealEngine和Unity。2)在金融交易系统中,C 的低延迟和高吞吐量使其成为首选,适用于高频交易和实时数据分析。

C XML库:比较和对比选项C XML库:比较和对比选项Apr 22, 2025 am 12:05 AM

C 中有四种常用的XML库:TinyXML-2、PugiXML、Xerces-C 和RapidXML。1.TinyXML-2适合资源有限的环境,轻量但功能有限。2.PugiXML快速且支持XPath查询,适用于复杂XML结构。3.Xerces-C 功能强大,支持DOM和SAX解析,适用于复杂处理。4.RapidXML专注于性能,解析速度极快,但不支持XPath查询。

C和XML:探索关系和支持C和XML:探索关系和支持Apr 21, 2025 am 12:02 AM

C 通过第三方库(如TinyXML、Pugixml、Xerces-C )与XML交互。1)使用库解析XML文件,将其转换为C 可处理的数据结构。2)生成XML时,将C 数据结构转换为XML格式。3)在实际应用中,XML常用于配置文件和数据交换,提升开发效率。

See all articles

热AI工具

Undresser.AI Undress

Undresser.AI Undress

人工智能驱动的应用程序,用于创建逼真的裸体照片

AI Clothes Remover

AI Clothes Remover

用于从照片中去除衣服的在线人工智能工具。

Undress AI Tool

Undress AI Tool

免费脱衣服图片

Clothoff.io

Clothoff.io

AI脱衣机

Video Face Swap

Video Face Swap

使用我们完全免费的人工智能换脸工具轻松在任何视频中换脸!

热工具

SecLists

SecLists

SecLists是最终安全测试人员的伙伴。它是一个包含各种类型列表的集合,这些列表在安全评估过程中经常使用,都在一个地方。SecLists通过方便地提供安全测试人员可能需要的所有列表,帮助提高安全测试的效率和生产力。列表类型包括用户名、密码、URL、模糊测试有效载荷、敏感数据模式、Web shell等等。测试人员只需将此存储库拉到新的测试机上,他就可以访问到所需的每种类型的列表。

mPDF

mPDF

mPDF是一个PHP库,可以从UTF-8编码的HTML生成PDF文件。原作者Ian Back编写mPDF以从他的网站上“即时”输出PDF文件,并处理不同的语言。与原始脚本如HTML2FPDF相比,它的速度较慢,并且在使用Unicode字体时生成的文件较大,但支持CSS样式等,并进行了大量增强。支持几乎所有语言,包括RTL(阿拉伯语和希伯来语)和CJK(中日韩)。支持嵌套的块级元素(如P、DIV),

WebStorm Mac版

WebStorm Mac版

好用的JavaScript开发工具

SublimeText3 Mac版

SublimeText3 Mac版

神级代码编辑软件(SublimeText3)

禅工作室 13.0.1

禅工作室 13.0.1

功能强大的PHP集成开发环境