字符串序列判定 - 华为OD统一考试（D卷）

OD统一考试（D卷）

分值： 100分

题解： Java / Python / C++

题目描述

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

判定规则:

• S中的每个字符在L中都能找到(可以不连续)，且S在L中字符的前后顺序与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

题解

这道题目的主要思路是遍历字符串L，在遍历的过程中，逐一比较L中的字符和S中的字符是否相等。如果相等，则S的索引前进一步，直到S的索引达到S的长度。在这个过程中，记录每次匹配成功时L中的索引位置。最后输出最后一个有效字符在L中的位置。

这种方法的时间复杂度是O(n)，其中n是字符串L的长度。因为每个字符只需要遍历一次。

注意，这个题目并不要求S在L中是连续的子串，只需要保持相对顺序一致即可。

给定的代码是用Java实现的，也提供了Python和C++的实现。

在Python的代码中，使用了input()函数获取输入字符串。

在C++的代码中，使用了cin来获取输入。

这些代码的基本逻辑是相同的，只是语法上有些差异。

Java

import java.util.Scanner;
/**
 * @author code5bug
 */
public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.nextLine(), t = sc.nextLine();

        int n1 = s.length(), n2 = t.length();
        int