2023年华为OD机考真题：最多提取子串数目

算法刷题3年前 (2023)更新江南白衣

全网最全面的华为OD机试真题汇总，100%原题题库，不需要开会员即可查看全部内容，更多考题请查看真题库。

真题库：https://www.yuque.com/codernav.com/od

题目：最多提取子串数目
知识点：字符串统计
时间限制：1s 空间限制：256MB 限定语言：不限
题目描述：
给定由 [a-z] 26个英文小写字母组成的字符串A和B，其中A中可能存在重复字母，B中不会存在重复字母
现从字符串A中按规则挑选一些字母，可以组成字符串B。
挑选规则如下：
1）同一个位置的字母只能被挑选一次
2）被挑选字母的相对先后顺序不能改变
求最多可以同时从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的字符串
行末无多余空格
补充说明：
无需验证输入格式和输入数据合法性
示例1
输入：
badc
bac
输出：
1
说明：
从字符串A(“badc”)中可以按字母相对先后顺序取出字符串B(“bac”)
示例2
输入：
badc
abc
输出：
0
说明：
从字符串A(“badc”)中无法按字母相对先后顺序取出字符串B(“abc”)
示例3
输入：
aabbcxd
abcd
输出：
1
说明：
从字符串A(“aabbcxd”)中挑选一组B(“abcd”)后，A中剩余字符串为”abx”，无法再挑出”abcd”
示例4
输入：
ababcecfdc
abc
输出：
2
说明：
按如下步骤（步骤不唯一），可以同时从字符串A(“ababcecfdc”)中最多取出两个B(“abc”)，其中下划线标注的是每步提取的字母：
剩余的”efdc”无法继续提取”abc”，结果为2
示例5
输入：
aaa
a
输出：
3
说明：
从字符串A(“aaa”)中可以挑选3个字符串B(“a”)
解题思路：
如示例4：
父字符串：ababcecfdc 父索引indexF=0
子字符串：abc 子索引indexS=0
indexF=0, indexS=0 a == a;
indexF+1=1, indexS+1=1 b == b
indexF+1=2, indexS+1=2 a != c
indexF+1=3, indexS=2 b ! = c
indexF+1=4, indexS=2 c == c
满足子串父字符串变为：ab ecfdc（匹配过的需要用空字符串替代）
indexF=0, indexS=0 a == a;
继续重复上面操作，直至indexF=父字符串长度-1

代码实现一：

package com.codernav.demo.hwod.exam;

import java.util.Scanner;

/**
 * @title 最多提取子串数目
 * @Description 给定由 [a-z] 26个英文小写字母组成的字符串A和B，其中A中可能存在重复字母，B中不会存在重复字母
 * 现从字符串A中按规则挑选一些字母，可以组成字符串B。
 * 挑选规则如下：
 * 1） 同一个位置的字母只能被挑选一次
 * 2） 被挑选字母的相对先后顺序不能改变
 * 求最多可以同时从A中挑选多少组能组成B的字符串
 * @Author 开发者导航
 * @website https://codernav.com
 * @date 2023/5/13
 */
public class Main{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String strF = sc.nextLine();    //父字符串
        String strS = sc.nextLine();    //子字符串
        char[] chars = strF.toCharArray();  //将父字符串转化为数组
        int indexF = 0;     //父字符串索引
        int indexS = 0;     //子字符串索引
        int count = 0;      //符合的个数
        while (indexF < strF.length()){
            if(chars[indexF] == strS.charAt(indexS)){
                chars[indexF] = ' ';    //已经匹配的置为空
                indexS++;
            }
            if(indexS == strS.length()){    //长度相同则表示符合子串
                indexS = 0;
                indexF = 0;
                count++;
            }else {
                indexF++;   //不符合则匹配下一个字符
            }
        }
        System.out.println(count);
    }

}

代码实现二：

package com.codernav.demo.hwod.exam;

import java.util.Scanner;

/**
 * @title 最多提取子串数目
 * @Description 给定由 [a-z] 26个英文小写字母组成的字符串A和B，其中A中可能存在重复字母，B中不会存在重复字母
 * 现从字符串A中按规则挑选一些字母，可以组成字符串B。
 * 挑选规则如下：
 * 1） 同一个位置的字母只能被挑选一次
 * 2） 被挑选字母的相对先后顺序不能改变
 * 求最多可以同时从A中挑选多少组能组成B的字符串
 * @Author 开发者导航
 * @website https://codernav.com
 * @date 2023/5/13
 */

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String stra = sc.nextLine();
        char[] x = stra.toCharArray();
        String strb = sc.nextLine();
        int[] arrs = new int[stra.length()];
        int index = 0;
        int count = 0;
        int i = 0;
        while (i < stra.length()) {
            if (x[i] == strb.charAt(index)) {
                arrs[index] = i + 1;
                index++;
                x[i] = '0';
            }

            if (index == strb.length()) {
                index = 0;
                i = arrs[0];
                count++;
            } else {
                i++;
            }
        }
        System.out.print(count);
    }
}