Московская городская олимпиада школьников по информатике,
2003/04 учебный год
при поддержке компаний
Задача J. Анаграммер
| Имя входного файла: | j.in |
| Имя выходного файла: | j.out |
| Максимальное время работы на одном тесте: | 2 секунды |
| Максимальный объем используемой памяти: | 8 мегабайт |
Анаграммер - специальное устройство для получения из слова его анаграмм (то есть слов, записанных теми же буквами, но в другом порядке). Это устройство умеет выполнять 2 операции:
1. Взять очередную букву исходного слова и поместить ее в стек.
2. Взять букву из стека и добавить ее в конец выходного слова.
Стек - это хранилище данных, которое работает по принципу "первый пришел - последний ушел". Стек можно представить себе в виде пирамидки. Когда мы добавляем букву в стек, это соответствует тому, что на стержень пирамидки сверху мы надеваем кольцо, на котором написана соответствующая буква. Когда берем букву из стека, то это соответствует тому, что мы снимаем со стержня верхнее кольцо, и смотрим, какая буква на нем написана.
Например, слово TROT в слово TORT может быть преобразовано анаграммером двумя различными последовательностями операций: 11112222 или 12112212.
Напишите программу, которая по двум заданным словам вычисляет количество различных последовательностей операций анаграммера, которые преобразуют первое из этих слов во второе, а также находит сами эти последовательности.
Формат входных данных
Первая строка входного файла содержит исходное слово, а вторая - слово, которое необходимо получить. Слова состоят только из заглавных латинских букв и имеют длину не более 50 символов. Оба слова имеют одинаковую длину. В этих строках не содержится пробелов.
Формат выходных данных
В первой строке выходного файла должно содержаться количество последовательностей операций анаграммера, с помощью которых можно преобразовать первое слово во второе.
Если это количество не превышает 1000, то в последующих строках должны содержаться сами последовательности. Каждая последовательность должна быть выведена на отдельной строке, и состоять из цифр 1 и 2 (указывающих порядок выполнения операций), выведенных без пробелов.
Примеры
| j.in | j.out |
MADAM ADAMM |
4 1111222122 1111222212 1121212122 1121212212 |
LONG GONG |
0 |
AAAAAAAA AAAAAAAA |
1430 |