【华为OD-E卷-最多提取子串数目 100分（python、java、c++、js、c）】
【华为OD-E卷-最多提取子串数目 100分（python、java、c++、js、c）】
题目
给定 [a-z]，26个英文字母小写字符串组成的字符串 A 和 B，其中 A 可能存在重复字母，B 不会存在重复字母，现从字符串 A 中按规则挑选一些字母，可以组成字符串B。
挑选规则如下：
同一个位置的字母只能挑选一次 被挑选字母的相对先后顺序不能被改变 求最多可以同时从 A 中挑选多少组能组成 B 的字符串。
输入描述
- 输入为 2 行，第 1 行输入字符串 A，第 2 行输入字符串 B，行首行尾没有多余空格，其中：
A、B 均由 [a-z] 26个英文小写字母组成 0 < A.length < 100，A 中可能包含重复字母 0 < B.length < 10，B 中不会出现重复字母
输出描述
- 输出 1 行，包含 1 个数字，表示最多可以同时从 A 中挑选多少组能组成 B 的字符串
行末没有多余空格
备注
- 无需验证输入格式和输入数据合法性
用例
用例一：
输入：
badc
bac
输出：
1
用例二：
输入：
badc
abc
输出：
0
用例三：
输入：
aabbcxd
abcd
输出：
1
用例四：
输入：
ababcecfdc
abc
输出：
2
python解法
- 解题思路：
- 这个代码的目标是找到字符串 b 在字符串 a 中可以组成的最多次完整匹配的次数，匹配过程是按照 b 中字符的顺序依次寻找并标记字符（标记为 ’ '），直到匹配完成一次。
具体步骤
将字符串 a 转为列表形式，以便逐字符修改。
初始化匹配计数 m 为 0。
在 _seek 方法中遍历 a，尝试按照 b 的字符顺序找到一次匹配。
找到匹配时，将匹配的字符从 a 中标记为空格 ’ '。
如果完成了一次完整的匹配，返回 True；否则返回 False。
在 find 方法中，循环调用 _seek 方法，每找到一次匹配，计数器 m 加 1，直到无法再找到完整匹配。
最终返回匹配次数 m。
class Comp:
def __init__(self, a, b):
# 初始化对象，将字符串 a 转为列表，便于修改其中的字符
self.a = list(a)
self.b = b
self.m = 0 # 匹配计数
def find(self):
# 计算字符串 b 在 a 中可以匹配的最大次数
while self._seek():
self.m += 1 # 每找到一次匹配，计数器加 1
return self.m
def _seek(self):
# 尝试在 a 中找到 b 的一次完整匹配
i, j = 0, 0 # i 遍历 a 的索引，j 遍历 b 的索引
while i < len(self.a):
if self.a[i] == self.b[j]: # 如果当前字符匹配
self.a[i] = ' ' # 标记已匹配的字符
j += 1 # 移动 b 的索引
if j == len(self.b): # 如果完成了一次完整匹配
return True
i += 1 # 移动 a 的索引
return False # 无法完成匹配
def run():
# 输入字符串 a 和 b
x = input()
y = input()
c = Comp(x, y) # 创建 Comp 对象
print(c.find()) # 输出匹配次数
if __name__ == "__main__":
run()
java解法
- 解题思路
- 这段代码的目标是计算字符串 pat 在字符串 txt 中可以按照顺序匹配的最大次数。匹配时，字符串 txt 的每个字符只能被匹配一次。通过一个辅助数组 used 记录 txt 中字符是否已经被使用，逐步完成匹配。
具体步骤
使用一个数组 used 标记 txt 中的字符是否已经被使用。
遍历 txt 字符，当发现字符可以和 pat 中当前需要匹配的字符对上时，标记为已使用。
完成一次匹配后，将匹配计数加 1，重置匹配索引，并从头开始检查 txt 中剩余未使用的字符，继续匹配。
重复此过程，直到无法完成更多匹配。
返回完成的匹配次数。
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in); // 创建输入流
String txt = sc.nextLine(); // 读取主串
String pat = sc.nextLine(); // 读取模式串
System.out.println(findMatches(txt, pat)); // 输出匹配次数
}
// 方法：计算模式串 pat 在主串 txt 中能匹配的最大次数
public static int findMatches(String txt, String pat) {
int len = txt.length(); // 主串的长度
int[] used = new int[len]; // 辅助数组，记录主串字符是否被使用
int pIdx = 0; // 模式串的索引
int cnt = 0; // 匹配计数
// 遍历主串
for (int tIdx = 0; tIdx < txt.length(); tIdx++) {
// 如果当前字符匹配且未被使用
if (txt.charAt(tIdx) == pat.charAt(pIdx) && used[tIdx] == 0) {
used[tIdx] = 1; // 标记当前字符为已使用
pIdx++; // 模式串索引向后移动
}
// 如果完成了一次完整匹配
if (pIdx == pat.length()) {
cnt++; // 匹配计数加 1
pIdx = 0; // 重置模式串索引
tIdx = -1; // 从主串开头重新遍历
}
}
return cnt; // 返回匹配次数
}
}
C++解法
- 解题思路
- 这段代码的目标是找到字符串 B 在字符串 A 中可以匹配的最大次数，每个字符匹配后将从 A 中标记为 ‘0’（已使用）。通过两次循环分别进行匹配检测和字符标记，逐步统计完成的匹配次数。
具体步骤
初始化：读取两个字符串 A 和 B，定义匹配计数器 count，以及索引变量 a_index 和 b_index。
匹配检测：
遍历字符串 A，按顺序检查是否可以找到 B 的完整子序列。
如果找到完整的 B，则增加计数器 count，退出循环；否则结束匹配过程。
字符标记：
从头遍历 A，将匹配的字符（与 B 对应的字符）标记为 ‘0’，表示该字符已被使用。
标记完成后，继续下一轮匹配检测，直到无法匹配为止。
输出结果：打印匹配计数器 count。
#include <iostream>
#include <string>
using namespace std;
int main() {
string A, B;
getline(cin, A); // 输入主串 A
getline(cin, B); // 输入模式串 B
int count = 0; // 记录匹配次数
size_t a_index = 0, b_index = 0; // 索引变量，用于遍历 A 和 B
// 循环查找 B 在 A 中的匹配
while (true) {
b_index = 0; // 每次匹配从 B 的第一个字符开始
for (size_t i = 0; i < A.size(); ++i) {
if (A[i] == B[b_index]) { // 当前字符匹配成功
++b_index; // 移动 B 的索引
if (b_index == B.size()) { // 如果完成了一次完整匹配
++count; // 匹配计数器加 1
break;
}
}
}
// 如果未能完成匹配，则结束循环
if (b_index != B.size()) {
break;
}
// 标记已匹配的字符为 '0'
size_t start = 0; // 用于追踪 B 的匹配起点
for (size_t i = 0; i < A.size(); ++i) {
if (A[i] == B[start]) { // 如果字符匹配
A[i] = '0'; // 标记为已使用
++start; // 移动 B 的起点
if (start == B.size()) { // 如果标记完成一次完整匹配
break;
}
}
}
}
cout << count << endl; // 输出匹配次数
return 0;
}
C解法
检查是否能找到 B 的完整匹配。
将匹配到的字符替换为 ‘0’（表示已使用），以便继续后续匹配。
#include <stdio.h>
#include <string.h>
int main() {
char A[1001], B[1001];
// 输入主串 A 和模式串 B
fgets(A, sizeof(A), stdin);
fgets(B, sizeof(B), stdin);
// 去掉换行符
A[strcspn(A, "\n")] = 0; // 去掉 A 的换行符
B[strcspn(B, "\n")] = 0; // 去掉 B 的换行符
int count = 0; // 记录匹配次数
while (1) {
int b_index = 0; // 用于遍历模式串 B
int found = 0; // 标志是否找到完整匹配
// 检查是否能找到 B 在 A 中的匹配
for (size_t i = 0; i < strlen(A); ++i) {
if (A[i] == B[b_index]) { // 如果当前字符匹配
++b_index; // 模式串索引后移
if (b_index == strlen(B)) { // 如果完成了一次完整匹配
++count; // 匹配次数加 1
found = 1; // 设置匹配标志
break;
}
}
}
// 如果未找到完整匹配，退出循环
if (b_index != strlen(B)) {
break;
}
// 替换 A 中匹配的字符为 '0'
size_t start = 0; // 记录 B 的匹配起点
for (size_t i = 0; i < strlen(A); ++i) {
if (A[i] == B[start]) { // 如果字符匹配
A[i] = '0'; // 替换为 '0' 表示已使用
++start; // 模式串索引后移
if (start == strlen(B)) { // 如果完成替换
break;
}
}
}
}
// 输出最终匹配次数
printf("%d\n", count);
return 0;
}
JS解法
字符替换：将字符串 seqA 转化为字符数组 charList，方便在匹配成功时标记字符为 ’ '（空格）。
匹配逻辑：
使用两个指针 posA 和 posB，分别遍历 seqA 和 seqB。
如果当前字符匹配，将其标记为 ’ '，并移动指针。
当完成一次完整匹配（posB === seqB.length）时，增加匹配计数器 matches。
终止条件：
如果无法完成匹配（即 posB < seqB.length 时退出循环）。
输入输出：
使用 readline 模块读取标准输入，获取两行字符串。
调用 countMatches 函数，输出匹配次数。
function countMatches(seqA, seqB) {
// 将 seqA 转为字符数组，方便标记已匹配字符
const charList = seqA.split('');
let matches = 0; // 记录匹配次数
while (true) {
let posA = 0; // 指针，用于遍历 charList
let posB = 0; // 指针，用于遍历 seqB
// 遍历 charList，查找 seqB 的匹配
while (posA < seqA.length) {
if (charList[posA] === seqB[posB]) { // 如果字符匹配
charList[posA] = ' '; // 标记该字符为已使用
posB += 1; // 移动 seqB 的指针
}
if (posB === seqB.length) { // 如果完成一次完整匹配
matches += 1; // 增加匹配计数
break; // 退出当前匹配循环
}
posA += 1; // 移动 seqA 的指针
}
// 如果无法完成匹配，结束外层循环
if (posB < seqB.length) {
break;
}
}
return matches; // 返回匹配次数
}
// 读取输入
const readline = require('readline');
const rl = readline.createInterface({
input: process.stdin,
output: process.stdout
});
let seqA = ''; // 存储第一行输入
let seqB = ''; // 存储第二行输入
rl.on('line', (input) => {
if (!seqA) { // 如果 seqA 未赋值
seqA = input;
} else { // 如果 seqA 已赋值，读取 seqB
seqB = input;
rl.close(); // 关闭输入流
}
});
rl.on('close', () => {
const result = countMatches(seqA, seqB); // 调用匹配函数
console.log(result); // 输出匹配结果
});
注意：
如果发现代码有用例覆盖不到的情况，欢迎反馈！会在第一时间修正，更新。
解题不易，如对您有帮助，欢迎点赞/收藏