AlgoMooc
← 返回题库

P3115. 有效子字符串

简单通过率 36% · 提交 1,264 · 通过 450
贪心双指针字符串

小慕正在处理两个字符串:一个叫 S,一个叫 L,它们都只包含小写字母。S 的长度不超过 100,L 的长度不超过 500000。小慕需要判断 S 是否是 L 的一个。 判定规则是:S 中的每一个字符,都能在 L 中按顺序找到(可以不连续),并且这些字符在 L 中出现的先后顺序必须与 S 中的顺序一致。 举个例子:S = "ace" 是 L = "abcde" 的一个有效,因为字符 a、c、e 在 L 中按顺序出现。而 "aec" 就不是有效子序列,因为 e 出现在 c 之前,顺序不一致,此时只有 a 和 e 符合位置要求。

提示:带虚线的词点一下有通俗解释。

输入描述

输入两个字符串S和L,都只包含小写字母,len(S) <= 100,len(L) <= 500000,先输入S再输入L 每个字符串占一行。

输出描述

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

示例

示例 1

输入

ace
abcde

输出

4

示例 2

输入

fgh
abcde

输出

-1

时间限制 1000 ms · 内存限制 128 MB

看不懂题目?点开图解(训练营专属)

登录后查看题目图解

题目图解为训练营学员专属内容,请先登录。

微信扫码登录还不是训练营学员?了解训练营 →
写完代码点「提交」,将对全部测试用例判题。