最短公共超串
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 512 M,其他语言1024 M
Special Judge, 64bit IO Format: %lld

题目描述

给定两个字符串 str_1 和 str_2 ,请返回同时以 str_1 和 str_2 作为子串的最短字符串。

称字符串 A 为另一个字符串 B 的子串,当且仅当将 B 的首部和尾部分别删除若干个字符(数量均可以为零)后得到 A 。例如, 等都是  的子串,而  不是。

输入描述:

输入共两行,每行一个只包含小写字母的字符串,分别表示  。(绝对值符号  表示字符串的长度)

输出描述:

输出一行一个字符串,表示同时以 str_1 和 str_2 作为子串的最短字符串。

如果存在多个答案,可以输出任意一个。
示例1

输入

复制
abac
cab

输出

复制
cabac

说明

对于样例1,可以证明没有比  更短的同时包含两个给定字符串作为子串的字符串了: 删掉最前面一个字符得到  ,删掉最后面两个字符得到 
示例2

输入

复制
bbbaaaba
bbababbb

输出

复制
bbababbbaaaba