2024年华为OD机试真题-字符串序列判定

华为OD机试真题-字符串序列判定-2024年OD统一考试（D卷）

题目描述：

输入两个字符串S和L，都只包含英文小写字母。S长度<=100，L长度<=500,000。判定S是否是L的有效字串。

判定规则：S中的每个字符在L中都能找到（可以不连续），且S在Ｌ中字符的前后顺序与S中顺序要保持一致。（例如，S="ace"是L="abcde"的一个子序列且有效字符是a、c、e，而"aec"不是有效子序列，且有效字符只有a、e）

输入描述：

输入两个字符串S和L，都只包含英文小写字母。S长度<=100，L长度<=500,000。先输入S，再输入L，每个字符串占一行。

输出描述：

S串最后一个有效字符在L中的位置。（首位从0开始计算，无有效字符返回-1）

补充说明：

示例1

输入：ace

abcde

输出：4

说明：

示例2

输入：fgh

abcde

输出：-1

解题思路：

这是一道字符串子序列匹配问题，查询某一字符串是否在另一字符串的子序列中，输出最后一个匹配的字符的位置，我们只需要顺序遍历s和l，模拟字符串的匹配，逐字符检查 s 是否作为 l 的子序列出现，并在找到匹配时更新索引位置。这种解法是线性的，因为它只需遍历一次字符串 l，使得时间复杂度为 O(n)，其中 n 是字符串 l 的长度。

Java解法：

import java.util.Scanner;
 
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String s = scanner.next(); // 读取第一个字符串到s
        String l = scanner.next(); // 读取第二个字符串到l
        scanner.close();
 
        int lastIdx = -1; // 初始化lastIdx为-1，表示找不到时的返回值
        int m = s.length(); // 获取字符串s的长度
        int n = l.length(); // 获取字符串l的长度
        int toMatch = 0;   // 初始化要匹配的位置为0