← 返回题目列表

Codeforces · 762/C

C. 两个字符串

中文机器翻译题面 查看原题

给定两个字符串 a 和 b。您必须从字符串 b 中删除尽可能少的连续(一个接一个)字符,使其成为字符串 a 的子序列。您可能根本不需要删除任何字符,或者您可能必须删除 b 中的所有字符并将其设为空。

字符串 s 的子序列是可以通过从字符串 s 中删除零个或多个字符(不一定是连续的)来获得的任何此类字符串。

输入

第一行包含字符串 a,第二行包含字符串 b。这两个字符串都是非空的,并且由英文字母的小写字母组成。每个字符串的长度不超过 105 个字符。

输出

在第一行输出字符串 a 的子序列,该子序列是通过删除 b 中最小数量的连续字符而获得的。

如果答案由零个字符组成,则输出“-”(减号)。

示例

输入 #1

hi
bob

输出 #1

-

输入 #2

abca
accepted

输出 #2

ac

输入 #3

abacaba
abcdcba

输出 #3

abcba

注意

在第一个示例中,字符串 a 和 b 不共享任何符号,因此您可以获得的最长字符串是空的。

在第二个例子中,ac是a的子序列,同时可以通过擦除字符串b中接受的连续符号来获得它。