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

25-03-07 19:02

2866

7247

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）的子序列出现多少次。
转化问题：通过将字符串a转化为列表来允许修改其内容，这样可以避免在后续匹配过程中重复使用相同的字符。
递归搜索：使用can_find函数来尝试在剩余的a中寻找b。如果找到，更新a的内容并递增计数器。
处理边界情况：当b的所有字符都被匹配后，can_find函数返回True，表示找到了一个新的子序列实例；否则，一旦a遍历完毕且没有完成匹配，返回False。
输出结果：最后，主程序调用find_seq函数并将结果输出。
这种方法虽然有效，但对于非常大的数据集可能效率较低，因为它需要多次遍历字符串。对于更高效的方法，可以考虑使用动态规划等算法来优化。

# 定义函数find_seq，用于计算字符串b作为子序列在字符串a中出现的次数
def find_seq(a, b):
    # 将字符串a转换为列表，以便于修改其中的字符
    lst = list(a)
    # 初始化计数器cnt为0
    cnt = 0

    # 当还可以在lst中找到b作为子序列时，继续循环
    while can_find(lst, b):
        # 每次找到一次完整的b作为子序列，就将计数器加1
        cnt += 1

    # 返回最终计数结果
    return cnt

# 辅助函数can_find，用来检查是否可以在当前状态下找到b作为lst的一个子序列
def can_find(lst, b):
    # pa是遍历lst的指针，pb是遍历b的指针
    pa = 0
    pb = 0

    # 遍历lst中的每个字符
    while pa < len(lst):
        # 如果lst[pa]与b[pb]匹配
        if lst[pa] == b[pb]:
            # 将匹配到的字符标记为空格（或可以设置为其他特殊符号），防止重复匹配
            lst[pa] = ' '
            # 移动b的指针
            pb += 1
        # 如果b已经被完整地匹配了一次
        if pb == len(b):
            # 则说明找到了b作为一个子序列，返回True
            return True
        # 不论是否匹配成功，都移动lst的指针
        pa += 1

    # 如果遍历完lst都没有完全匹配到b，则返回False
    return False

# 从用户获取输入
a = input()  # 输入字符串a
b = input()  # 输入字符串b

# 调用find_seq函数，并打印结果
res = find_seq(a, b)
print(res)  # 输出b作为子序列在a中出现的次数
 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

java解法

解题思路
读取输入：从标准输入读取两个字符串，一个是父字符串parent，另一个是子字符串child。
初始化：创建一个数组matched来记录每个字符是否已经被用作匹配的一部分。这个数组的大小与parent字符串相同。
遍历父字符串：使用一个循环遍历parent中的每个字符。
尝试匹配：对于每一个字符，尝试去匹配child中的字符。如果匹配成功并且该字符尚未被标记为已匹配，则将matched数组中对应位置设置为1，并移动child的指针。
计数：如果child中的所有字符都被匹配到，则增加计数器count，并重置外层循环索引i以重新开始匹配。
输出结果：最后，输出计数器count的值，即child作为子序列在parent中出现的次数。

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        // 读取输入的两个字符串
        String parent = sc.nextLine(); // 父字符串
        String child = sc.nextLine();  // 子字符串

        int length = parent.length();
        // matched数组用于记录parent中每个字符是否已被匹配过
        int[] matched = new int[length];

        int count = 0;  // 计算子序列出现次数
        for (int i = 0; i < length; ) {  // 遍历父字符串
            int j = 0;  // 子字符串的索引
            while (i < length && j < child.length()) {  // 尝试匹配
                if (parent.charAt(i) == child.charAt(j) && matched[i] == 0) {  // 如果字符匹配且未被标记
                    matched[i] = 1;  // 标记当前字符
                    j++;  // 移动子字符串指针
                }
                i++;  // 移动父字符串指针
            }
            if (j == child.length()) {  // 如果子字符串完全匹配
                count++;  // 增加计数
                i = -1;  // 重置i，以便从头开始新的匹配
            }
        }

        System.out.println(count);  // 输出最终计数
    }
}
 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

C++解法

解题思路
1. 题目要求统计字符串 B 在字符串 A 中作为子序列出现的次数。
2. 使用循环遍历字符串 A，从中找出与 B 匹配的子序列。
3. 每找到一次匹配，更新计数并将匹配到的字符替换为 '0'，这样可以避免重复使用相同的字符进行下次匹配。
4. 重复查找直到无法找到完整匹配的 B。
这种解法通过逐步替换已匹配的字符来实现多次匹配，确保每个字符不会被重复使用。

#include 
#include 
using namespace std;

int main() {
    string A, B;
    // 从输入读取两个字符串 A 和 B
    getline(cin, A);
    getline(cin, B);

    int count = 0; // 记录 B 在 A 中出现的次数
    size_t a_index = 0, b_index = 0;

    // 循环查找字符串 B 在 A 中的出现次数
    while (true) {
        b_index = 0;
        // 遍历字符串 A，查找与 B 匹配的子序列
        for (size_t i = 0; i < A.size(); ++i) {
            if (A[i] == B[b_index]) { // 当 A 中字符与 B 中字符匹配时
                ++b_index; // 移动 B 的指针
                if (b_index == B.size()) { // 如果 B 中所有字符都匹配成功
                    ++count; // 增加匹配计数
                    break; // 退出当前匹配循环
                }
            }
        }

        // 如果 B 没有完全匹配，则结束循环
        if (b_index != B.size()) {
            break;
        }

        // 将已匹配的部分替换为 '0'，避免重复匹配
        size_t start = 0;
        for (size_t i = 0; i < A.size(); ++i) {
            if (A[i] == B[start]) { // 当找到匹配字符时
                A[i] = '0'; // 将 A 中匹配的字符替换为 '0'
                ++start; // 移动 B 的指针
                if (start == B.size()) { // 如果所有字符都被匹配并替换
                    break; // 结束替换过程
                }
            }
        }
    }

    // 输出 B 在 A 中的出现次数
    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
48
49
50

C解法

解题思路
1. 从输入读取字符串 A 和 B，并去掉末尾的换行符，以方便后续处理。
2. 使用循环遍历字符串 A，查找字符串 B 作为子序列出现的次数。
3. 每找到一次完整匹配的 B，将匹配到的字符替换为 '0'，避免重复匹配同样的字符。
4. 当无法找到完整匹配的 B 时结束循环，输出匹配次数。
通过逐步替换已匹配的字符确保同一个字符不会被重复使用，从而准确统计 B 作为子序列在 A 中的出现次数。

#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;
    B[strcspn(B, "\n")] = 0;

    int count = 0; // 记录 B 在 A 中的出现次数

    while (1) {
        int b_index = 0;
        int found = 0;

        // 检查是否能找到 B 作为子序列在 A 中出现
        for (size_t i = 0; i < strlen(A); ++i) {
            if (A[i] == B[b_index]) { // 当 A 中字符与 B 中字符匹配时
                ++b_index; // 移动 B 的指针
                if (b_index == strlen(B)) { // 如果 B 中所有字符都匹配成功
                    ++count; // 增加匹配计数
                    found = 1; // 标记找到了 B
                    break; // 退出当前匹配循环
                }
            }
        }

        // 如果没有找到完整的 B，则结束循环
        if (b_index != strlen(B)) {
            break;
        }

        // 将已匹配的部分替换为 '0'，避免重复匹配
        size_t start = 0;
        for (size_t i = 0; i < strlen(A); ++i) {
            if (A[i] == B[start]) { // 当找到匹配字符时
                A[i] = '0'; // 将 A 中匹配的字符替换为 '0'
                ++start; // 移动 B 的指针
                if (start == strlen(B)) { // 如果所有字符都被匹配并替换
                    break; // 结束替换过程
                }
            }
        }
    }

    // 输出 B 在 A 中的出现次数
    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解法

解题思路
1. 使用 matchCount 函数计算字符串 B 在字符串 A 中作为子序列出现的次数。
2. 将字符串 A 转换为字符数组，方便在找到匹配后标记字符。
3. 使用 findMatch 函数在字符数组中查找 B 的匹配，匹配成功后将匹配的字符标记为空格，防止重复使用。
4. 重复查找，直到无法找到完整的匹配，最后返回匹配的次数。
5. 使用 readline 模块从标准输入读取字符串 A 和 B，计算匹配次数并输出结果

// 计算字符串 B 在字符串 A 中作为子序列出现的次数
function matchCount(strA, strB) {
    const chars = strA.split(''); // 将字符串 A 转换为字符数组，方便修改
    let count = 0; // 记录 B 在 A 中的出现次数

    // 不断查找字符串 B，直到找不到为止
    while (true) {
        if (!findMatch(chars, strB)) break; // 如果找不到匹配则退出循环
        count++; // 找到一次完整匹配，计数加一
    }

    return count; // 返回匹配次数
}

// 查找 B 作为子序列在 A 中的匹配，并标记已匹配的字符
function findMatch(chars, strB) {
    let idxA = 0; // 字符数组 A 的索引
    let idxB = 0; // 字符串 B 的索引

    // 遍历字符数组 A
    while (idxA < chars.length) {
        if (chars[idxA] === strB[idxB]) { // 当字符匹配时
            chars[idxA] = ' '; // 将已匹配的字符标记为空格，避免重复使用
            idxB++; // 移动 B 的指针
        }
        if (idxB === strB.length) { // 如果 B 中所有字符都匹配成功
            return true; // 返回找到匹配
        }
        idxA++; // 移动 A 的指针
    }

    return false; // 如果没有找到完整的 B，返回 false
}

const readline = require('readline');
const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
});

let inputA = '';
let inputB = '';

// 从标准输入读取两个字符串
rl.on('line', (input) => {
    if (!inputA) {
        inputA = input; // 读取第一个字符串 A
    } else {
        inputB = input; // 读取第二个字符串 B
        rl.close();
    }
});

// 当输入完成后，计算匹配次数并输出结果
rl.on('close', () => {
    const result = matchCount(inputA, inputB);
    console.log(result); // 输出 B 在 A 中的出现次数
});

 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
57
58
59

注意：

如果发现代码有用例覆盖不到的情况，欢迎反馈！会在第一时间修正，更新。

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

复制链接

发表评论

注册

评论记录：

未查询到任何数据！