Игра со словами
Первоисточник: http://ctddev.ifmo.ru/school/io/archive.html
Задачу добавил: alef
Успешно сдано решений: 8
Девочка Катя любит разные игры со словами. Недавно она придумала новую игру. Увидев где-либо написанное слово, она пытается придумать предложение, содержащее это слово в себе. Буквы увиденного слова должны идти в предложении по порядку, но не обязательно подряд. Например, увидев слово "LTIBE", она придумывает предложение "LET IT BE". Разумеется, Катя ищет кратчайшее предложение.
Ваша задача помочь Кате, автоматизировав игру.
Формат входного файла
В первой строке содержится увиденное Катей слово. Слово состоит из заглавных латинских букв. Его длина не менее 1 символа и не более 500. Во второй строке входного файла записано целое число N (1<=N<=500) - количество слов в словарном запасе Кати. Далее в N строках записаны слова. Слова состоят из заглавных латинских букв, содержат не менее 1 и не более 50 букв. Слова в наборе могут совпадать. В искомом предложении слово может использоваться любое количество раз, главное, чтобы оно содержалось в списке.
Формат выходного файла
Выведите искомое предложение. Слова в предложении разделяйте пробелами. Длиной
предложения называется количество символов (включая пробелы) использующихся при его записи.
Переведите в нижний регистр те символы, которые образуют заданное слово. Если решений несколько, выведите любое. Если решения не существует, выведите в выходной файл символ *.
Пример входного файла
LTIBE
5
IT
THE
LET
BEE
BE
Пример выходного файла
lEt iT be
Пример входного файла
TBONTOBE
4
OR
BE
TO
NOT
Пример выходного файла
tO bE oR nOt To be