在本文中,我们将深入研究计算机科学领域中一个独特且令人着迷的问题 - “计算字符串中恰好出现 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中文网其他相关文章!

Gulc是一个高性能的C库,优先考虑最小开销,积极的内衬和编译器优化。 其设计非常适合高频交易和嵌入式系统等关键应用程序,其设计强调简单性,模型

本文详细介绍了C函数返回类型,包括基本(int,float,char等),派生(数组,指针,结构)和void类型。 编译器通过函数声明和返回语句确定返回类型,执行

本文解释了C函数声明与定义,参数传递(按值和指针),返回值以及常见的陷阱,例如内存泄漏和类型不匹配。 它强调了声明对模块化和省份的重要性

本文详细介绍了字符串案例转换的C功能。 它可以通过ctype.h的toupper()和tolower()解释,并通过字符串迭代并处理零终端。 常见的陷阱,例如忘记ctype.h和修改字符串文字是

本文研究C函数返回值存储。 较小的返回值通常存储在寄存器中以备速度;较大的值可能会使用指针来记忆(堆栈或堆),影响寿命并需要手动内存管理。直接ACC

本文分析了形容词“独特”的多方面用途,探索其语法功能,常见的短语(例如,“不同于”,“完全不同”),以及在正式与非正式中的细微应用

本文解释了C标准模板库(STL),重点关注其核心组件:容器,迭代器,算法和函子。 它详细介绍了这些如何交互以启用通用编程,提高代码效率和可读性t

本文详细介绍了c中有效的STL算法用法。 它强调了数据结构选择(向量与列表),算法复杂性分析(例如,std :: sort vs. std vs. std :: partial_sort),迭代器用法和并行执行。 常见的陷阱


热AI工具

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

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

Undress AI Tool
免费脱衣服图片

Clothoff.io
AI脱衣机

AI Hentai Generator
免费生成ai无尽的。

热门文章

热工具

安全考试浏览器
Safe Exam Browser是一个安全的浏览器环境,用于安全地进行在线考试。该软件将任何计算机变成一个安全的工作站。它控制对任何实用工具的访问,并防止学生使用未经授权的资源。

DVWA
Damn Vulnerable Web App (DVWA) 是一个PHP/MySQL的Web应用程序,非常容易受到攻击。它的主要目标是成为安全专业人员在合法环境中测试自己的技能和工具的辅助工具,帮助Web开发人员更好地理解保护Web应用程序的过程,并帮助教师/学生在课堂环境中教授/学习Web应用程序安全。DVWA的目标是通过简单直接的界面练习一些最常见的Web漏洞,难度各不相同。请注意,该软件中

SublimeText3 英文版
推荐:为Win版本,支持代码提示!

EditPlus 中文破解版
体积小,语法高亮,不支持代码提示功能

SublimeText3 Linux新版
SublimeText3 Linux最新版