Задачи
Слияние строк
Слияние строк
Имеются две строки A и B.
Ваша задача - найти такую строку C, которая содержит в себе и A и B в качестве подстрок и является кратчайшей среди всех таких возможных строк.
Подстрокой строки называется последовательно идущая подпоследовательность этой строки. Например, строка kbtu является подстрокой строки kbtu open, но строка fall подстрокой не является.
Входные данные
Первая строка содержит строку A (1 ≤ |A| ≤ 10^5
).
Вторая строка содержит строку B (1 ≤ |B| ≤ 10^5
).
Гарантируется, что обе строки содержат только строчные латинские буквы.
Выходные данные
Выведите одну строку C.
Пример
Входные данные #1
compressing single
Выходные данные #1
compressingle
Входные данные #2
can you
Выходные данные #2
youcan
Входные данные #3
compressiondoneright doner
Выходные данные #3
compressiondoneright