题目描述：字符串序列判定/最后一个有效字符

输入两个字符串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）

示例：

用例解析

在上面的用例中，indexS和indexL是通过循环逐步变化的。下面是它们的具体变化过程：

1. 初始化索引：
   indexS = 0, indexL = 0

第一次循环：

• 检查S中的第一个字符’a’与L中的第一个字符’a’是否相同，相同则indexS加1，indexL加1。
• indexS = 1, indexL = 1

第二次循环：

• 检查S中的第二个字符’c’与L中的第二个字符’b’是否相同，不同则indexS不变，indexL加1。
• indexS = 1, indexL = 2

第三次循环：

• 检查S中的第二个字符’c’与L中的第三个字符’c’是否相同，相同则则indexS加1，indexL加1。
• indexS = 2, indexL = 3

第四次循环：

• 检查S中的第三个字符’e’与L中的第四个字符’d’是否相同，不同则indexS不变，indexL加1。
• indexS = 2, indexL = 4

1. 第五次循环：

   • S已经遍历完，循环结束。

在循环结束后，判断indexS是否等于S的长度，即判断S的所有字符是否都在L中找到了。在这个用例中，indexS等于S的长度，表示S中的字符都在L中找到了。

最后，打印L中最后一个有效字符的位置（即L的当前索引减1），即输出为4。

Python算法源码

# 从标准输入读取两个字符串
stringS = input()
stringL = input()

# 初始化两个索引，分别用于遍历S和L
indexS = 0
indexL = 0

# 当S和L都没有遍历完时，继续遍历
while indexS < len(stringS) and indexL < len(stringL):
    # 如果S中的当前字符与L中的当前字符相同，则S的索引加1
    if stringS[indexS] == stringL[indexL]:
        indexS += 1
    # 无论字符是否相同，L的索引都加1
    indexL += 1

# 如果S的所有字符都在L中找到了（即S已经遍历完了），则打印L中最后一个有效字符的位置（即L的当前索引减1）
if indexS == len(stringS):
    print(indexL - 1)
# 如果S还有字符没有在L中找到，则打印-1
else:
    print(-1)

C算法源码

#include <stdio.h>
#include <string.h>

int main() {
    char stringS[1000], stringL[1000];
    fgets(stringS, sizeof(stringS), stdin);
    fgets(stringL, sizeof(stringL), stdin);

    // 去除字符串末尾的换行符
    stringS[strcspn(stringS, "\n")] = '\0';
    stringL[strcspn(stringL, "\n")] = '\0';

    // 初始化两个索引，分别用于遍历S和L
    int indexS = 0;
    int indexL = 0;

    // 当S和L都没有遍历完时，继续遍历
    while (stringS[indexS] != '\0' && stringL[indexL] != '\0') {
        // 如果S中的当前字符与L中的当前字符相同，则S的索引加1
        if (stringS[indexS] == stringL[indexL]) {
            indexS++;
        }
        // 无论字符是否相同，L的索引都加1
        indexL++;
    }

    // 如果S的所有字符都在L中找到了（即S已经遍历完了），则打印L中最后一个有效字符的位置（即L的当前索引减1）
    if (stringS[indexS] == '\0') {
        printf("%d\n", indexL - 1);
    }
    // 如果S还有字符没有在L中找到，则打印-1
    else {
        printf("-1\n");
    }

    return 0;
}

Java算法源码

import java.util.Scanner;

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

        String stringS = scanner.nextLine();
        String stringL = scanner.nextLine();

        // 初始化两个索引，分别用于遍历S和L
        int indexS = 0;
        int indexL = 0;

        // 当S和L都没有遍历完时，继续遍历
        while (indexS < stringS.length() && indexL < stringL.length()) {
            // 如果S中的当前字符与L中的当前字符相同，则S的索引加1
            if (stringS.charAt(indexS) == stringL.charAt(indexL)) {
                indexS++;
            }
            // 无论字符是否相同，L的索引都加1
            indexL++;
        }

        // 如果S的所有字符都在L中找到了（即S已经遍历完了），则打印L中最后一个有效字符的位置（即L的当前索引减1）
        if (indexS == stringS.length()) {
            System.out.println(indexL - 1);
        }
        // 如果S还有字符没有在L中找到，则打印-1
        else {
            System.out.println(-1);
        }
    }
}