Description

子串是⼀个字符串中连续的⼀部分，

而子列是字符串中保持字符顺序的⼀个子集，可以连续也可以不连续。

例如给定字符串 atpaaabpabtt，pabt是⼀个子串，而pat 就是⼀个子列。

现给定⼀个字符串 S 和⼀个子列 P，本题就请你找到 S 中包含 P 的最短⼦串。

若解不唯一，则输出起点最靠左边的解。

Input Format

输入在第一行中给出字符串 S，第二行给出 P。

S 非空，由不超过 104 个小写英文字母组成；P 保证是 S 的⼀个⾮空⼦列。

Output Format

在一行中输出 S 中包含 P 的最短子串。

若解不唯一，则输出起点最靠左边的解。

atpaaabpabttpcat
pat

pabt

Source