Задача D. Составление строк

Автор:А. Кленин   Ограничение времени:5 сек
Входной файл:input.txt   Ограничение памяти:64 Мб
Выходной файл:output.txt  

Условие

Назовем строку A составленной из строки B, если каждый символ строки A встречается в строке B по меньшей мере столько же раз, сколько и в A. Например, строка abac является составленной из строки ccbada, а строка abba — нет.

Даны две текстовые строки. Требуется найти самую длинную подстроку первой строки, составленную из второй.

Формат входного файла

В первой строке входного файла содержится первая строка, во второй — вторая строка.

Формат выходного файла

Выходной файл должен содержать одну самую длинную подстроку. Если найдено несколько подстрок одинаковой длины, следует вывести ту, которая встречается раньше. Входные данные таковы, что первая строка обязательно содержит хотя бы один символ из второй.

Ограничения

Длина каждой строки — от 1 до 255 символов.

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
dabcxxdxbb
xbbc
bcx

0.028s 0.007s 15