【华为OD-E卷-16 最多提取子串数目 100分（python、java、c++、js、c）】

25-03-07 19:03

2102

12760

blog.csdn.net

id="article_content" class="article_content clearfix" style="height: 2000px; overflow: hidden;"> id="content_views" class="markdown_views prism-tomorrow-night">

【华为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
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">

1
2

输出：

1
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">

1

用例二：

输入：

badc
abc
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">

1
2

输出：

0
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">

1

用例三：

输入：

aabbcxd
abcd
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">

1
2

输出：

1
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">

1

用例四：

输入：

ababcecfdc
abc
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">1
2

输出：

2
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">1

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()

 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

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; // 返回匹配次数
    }
}

 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

C++解法

解题思路
这段代码的目标是找到字符串 B 在字符串 A 中可以匹配的最大次数，每个字符匹配后将从 A 中标记为 ‘0’（已使用）。通过两次循环分别进行匹配检测和字符标记，逐步统计完成的匹配次数。

具体步骤
初始化：读取两个字符串 A 和 B，定义匹配计数器 count，以及索引变量 a_index 和 b_index。
匹配检测：
遍历字符串 A，按顺序检查是否可以找到 B 的完整子序列。
如果找到完整的 B，则增加计数器 count，退出循环；否则结束匹配过程。
字符标记：
从头遍历 A，将匹配的字符（与 B 对应的字符）标记为 ‘0’，表示该字符已被使用。
标记完成后，继续下一轮匹配检测，直到无法匹配为止。
输出结果：打印匹配计数器 count。

#include 
#include 
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;
}

 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

C解法

解题思路
这段代码的目标是计算字符串 B 在字符串 A 中最多能匹配的次数，匹配要求 B 的每个字符按顺序在 A 中出现，且已匹配的字符不能被重复使用。为了实现这一目标，代码分为两步：

检查是否能找到 B 的完整匹配。
将匹配到的字符替换为 ‘0’（表示已使用），以便继续后续匹配。

#include 
#include 

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;
}

 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

JS解法

解题思路
这段代码的目标是计算字符串 seqB 在字符串 seqA 中最多可以按照顺序完整匹配的次数，每次匹配时，字符串 seqA 的字符只能使用一次。主要的实现逻辑分为以下几个部分：

字符替换：将字符串 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); // 输出匹配结果
});

 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56

注意：

如果发现代码有用例覆盖不到的情况，欢迎反馈！会在第一时间修正，更新。
解题不易，如对您有帮助，欢迎点赞/收藏

注：本文转载自blog.csdn.net的CodeClimb的文章"https://blog.csdn.net/CodeClimb/article/details/144538057"。版权归原作者所有，此博客不拥有其著作权，亦不承担相应法律责任。如有侵权，请联系我们删除。

复制链接

发表评论

注册

评论记录：

未查询到任何数据！