P3115. 有效子字符串

解题思路

与 的异同

注意，本题和 判断子序列 几乎完全一致。唯一的不同之处在于本题不仅要判断 S 能够由 L 构成，还要得到 S 串最后一个有效字符在 L 中的位置。这实际上进一步提醒我们应该用 贪心思想 来解决这个问题。

特殊示例说明

需要特别注意，经过同学考试测试，对于例子：

应该输出：

这是因为，S = "he" 虽然在 L = "ehh" 中不能够完全匹配，但是能够匹配第一个字符 "h"，这个 "h" 是 S 的最后一个有效字符，在 L 中第一次出现的位置是 1，故输出答案为 1。

也就是说，题目要求寻找的字符，是按照 S 中的顺序，在 S 中最后一个出现在 L 中的字符，但并不要求 S 的最后一个字符一定要出现在 L 中。这和 判断子序列 的要求略有不同，但是在代码上是非常接近的。

贪心思想的应用

仅需一个简单的例子就可以看出为何要使用 贪心思想：假设 L = "abac"，S = "abc"。当我们做字符匹配时，当然会选择 L 中的第一个 "a" 而不是第二个 "a" 来与 S 中的 "a" 进行匹配。因为只有选择了尽量靠前的 "a"，才能使得 S 更有可能由 L 中的字符按照顺序构成。

双指针算法

故我们只需设置两个 同向双指针 pl 和 ps，分别用于 L 和 S 从左到右的遍历。当：

• S[ps] == L[pl] 时，说明当前 L 中字符能与 S 匹配，此时应该记录 ans = pl，是当前遇到的 S 中的最新的一个有效字符在 L 中的索引，同时 pl 和 ps 各自前进。
• S[ps] != L[pl] 时，说明当前 L 中字符不能与 S 匹配，此时 ps 不应该移动，pl 前进一位，去寻找 L 中下一个能和 S[ps] 匹配的字符。

上述过程应该在一个 while 循环 中进行，退出循环的条件是 pl 到达 L 末尾 nl 或者 ps 到达 S 末尾 ns。故上述算法的主体代码为：

初始化与输出

我们可以初始化 ans 为 -1，那么只要在循环中没有进入 if S[ps] == L[pl] 的分支，就说明 S 中没有任意一个字符能够跟 L 进行匹配，最终结果应该为 -1。最终输出 ans 即可。

复杂度分析

• 设 L 的长度为 nl、S 的长度为 ns。while 循环每轮 pl 必定前进一位（匹配与否都会移动），ps 只在匹配成功时前进，所以循环至多执行 nl 轮，时间复杂度为 O(nl)。题面给出 L 长度不超过 500000、S 不超过 100，一次线性扫描即可完成。
• ps 的移动总量不超过 ns，被 O(nl) 覆盖，不构成额外项。
• 除两个输入字符串外，只用了 ans 与四个整型变量（ns、nl、ps、pl），辅助空间为 O(1)。
• 这也是「能匹配就立刻匹配」这一贪心策略的好处：L 中每个字符只被查看一次、无需回溯，50 万规模的 L 也能轻松处理；正文已论证匹配尽量靠前的字符不会让后续匹配变差，所以线性一遍即为最优。