数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
服装设计
法律研究统计字符串中出现恰好 K 次的 M 长度子字符串
在本文中，我们将深入探讨计算机科学领域一个独特而有趣的问题——“统计字符串中出现恰好 K 次的 M 长度子字符串”。这类问题在编程竞赛和面试中经常遇到。在开始之前，让我们先定义一下我们要处理的内容：
子字符串 − 在另一个字符串中找到的连续序列。
M 长度 − 我们感兴趣的子字符串的长度。
K 次 − 子字符串在原始字符串中出现的精确次数。
算法解释
为了解决这个问题，我们将利用哈希映射（在 C++ 中也称为无序映射）的功能。哈希映射允许我们将数据存储在键值对中，并为搜索和插入操作提供常数时间复杂度，这使得它们成为解决此类问题的绝佳工具。
统计字符串中出现恰好 K 次的 M 长度子字符串的算法如下：
初始化一个空的哈希映射。
遍历字符串，创建所有可能的 M 长度子字符串。
对于每个子字符串，将其添加到哈希映射中。如果它已经存在，则递增其计数。
在所有子字符串都被计数之后，遍历哈希映射以查找所有出现恰好 K 次的子字符串。
C++ 实现
以下是上述算法的 C++ 实现：
示例
以下是实现上述算法的程序：
#include <stdio.h>
#include <string.h>
int countSubstrings(char *s, int M, int K) {
char substr[M + 1]; // Array to hold the current substring
int n = strlen(s); // Length of the input string
int count = 0; // Variable to store the count of valid substrings
// Loop through the string to find substrings
for (int i = 0; i <= n - M; i++) {
strncpy(substr, s + i, M); // Copy M characters from the current position
substr[M] = '\0'; // Null-terminate the substring
int freq = 1; // Initialize frequency of the current substring
// Count the frequency of the current substring in the rest of the string
for (int j = i + 1; j <= n - M; j++) {
if (strncmp(substr, s + j, M) == 0) {
freq++;
}
}
if (freq == K) {
count++; // Increment count if frequency matches K
}
}
return count;
}
int main() {
char s[] = "abcabcabc";
int M = 3;
int K = 3;
int result = countSubstrings(s, M, K);
printf("The number of M length substring occurring exactly K times is: %d\n", result);
return 0;
}
输出
The number of M-length substrings occurring exactly K times is: 1
#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
import java.util.HashMap;
import java.util.Map;
public class Main {
public static int countSubstrings(String s, int M, int K) {
Map<String, Integer> countMap = new HashMap<>(); // Map to store substring frequencies
int n = s.length(); // Length of the input string
// Loop through the string to find substrings
for (int i = 0; i <= n - M; i++) {
String substring = s.substring(i, i + M); // Extract the current substring
countMap.put(substring, countMap.getOrDefault(substring, 0) + 1); // Update substring frequency
}
int count = 0;
// Count the substrings with frequency equal to K
for (int freq : countMap.values()) {
if (freq == K) {
count++;
}
}
return count;
}
public static void main(String[] args) {
String s = "abcabcabc";
int M = 3;
int K = 3;
int result = countSubstrings(s, M, K);
System.out.println("The number of M length substring occurring exactly K times is: " + result);
}
}
输出
The number of M-length substrings occurring exactly K times is: 1
def count_substrings(s, M, K):
count_map = {} # Dictionary to store substring frequencies
n = len(s) # Length of the input string
# Loop through the string to find substrings
for i in range(n - M + 1):
substring = s[i:i+M] # Extract the current substring
if substring in count_map:
count_map[substring] += 1
else:
count_map[substring] = 1
count = 0
# Count the substrings with frequency equal to K
for freq in count_map.values():
if freq == K:
count += 1
return count
def main():
s = "abcabcabc"
M = 3
K = 3
result = count_substrings(s, M, K)
print("The number of M length substring occurring exactly K times is:", result)
if __name__ == "__main__":
main()
输出
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++ 中实现了一个有效的解决方案，它为我们提供了常数时间的搜索和插入操作。这个问题是数据结构和算法如何结合起来有效地解决复杂问题的完美示例。
368 次浏览
