用c++语言编程:给定一个字符串A和一个字符串B,找到B在A中的最小子串,它将包含B中的所有字符。
时间: 2024-06-08 15:10:13 浏览: 216
查找字符串中最小字符串-C语言代码
你可以使用滑动窗口算法来解决这个问题。下面是一个用C语言实现的示例代码:
```c
#include <stdio.h>
#include <string.h>
#define MAX_CHARS 256
// 判断两个字符数组是否相等
int isSame(int countP[], int countQ[]) {
for (int i = 0; i < MAX_CHARS; i++) {
if (countP[i] != countQ[i]) {
return 0;
}
}
return 1;
}
void findMinSubstring(char A[], char B[]) {
int lenA = strlen(A);
int lenB = strlen(B);
if (lenA < lenB) {
printf("No such window exists");
return;
}
// 统计B中每个字符出现的次数
int countB[MAX_CHARS] = {0};
for (int i = 0; i < lenB; i++) {
countB[B[i]]++;
}
// 统计A中每个字符出现的次数
int countA[MAX_CHARS] = {0};
int start = 0, startIndex = -1, minLength = INT_MAX;
int count = 0;
for (int j = 0; j < lenA; j++) {
// 统计A中每个字符出现的次数
countA[A[j]]++;
// 找到B中的所有字符
if (countB[A[j]] != 0 && countA[A[j]] <= countB[A[j]]) {
count++;
}
// 如果找到了B中的所有字符
if (count == lenB) {
// 移除多余的字符
while (countA[A[start]] > countB[A[start]] || countB[A[start]] == 0) {
if (countA[A[start]] > countB[A[start]]) {
countA[A[start]]--;
}
start++;
}
// 更新最小长度和起始索引
int windowLen = j - start + 1;
if (windowLen < minLength) {
minLength = windowLen;
startIndex = start;
}
}
}
// 没有找到符合条件的子串
if (startIndex == -1) {
printf("No such window exists");
return;
}
// 打印最小子串
for (int k = startIndex; k < startIndex + minLength; k++) {
printf("%c", A[k]);
}
}
int main() {
char A[] = "ADOBECODEBANC";
char B[] = "ABC";
findMinSubstring(A, B);
return 0;
}
```
这个示例代码中,我们通过滑动窗口算法来寻找在字符串A中包含字符串B的最小子串。我们使用两个字符数组`countA`和`countB`来分别统计字符串A和B中每个字符出现的次数。然后,我们使用两个指针`start`和`startIndex`来表示窗口的起始位置,以及一个变量`minLength`来记录当前找到的最小子串的长度。我们逐步向右移动指针,更新窗口内的字符计数,并在窗口内找到了所有B中的字符时进行处理。如果找到了比当前最小子串长度更小的子串,我们更新`minLength`和`startIndex`。最后,我们打印出最小子串。
对于给定的示例输入,上述代码将输出 "BANC",这是字符串A中包含字符串B的最小子串。
阅读全文