Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Алгоритмы
Курсы ККДП
Дистрибутивы
Ссылки

HotLog


 

Анаграммер

(Время: 1 сек. Память: 16 Мб Сложность: 75%)

Анаграммер — специальное устройство для получения из слова его анаграмм (то есть слов, записанных теми же буквами, но в другом порядке). Это устройство умеет выполнять 2 операции:

  1. Взять очередную букву исходного слова и поместить ее в стек.
  2. Взять букву из стека и добавить ее в конец выходного слова.

Стек — это хранилище данных, которое работает по принципу "первый пришел — последний ушел". Стек можно представить себе в виде пирамидки. Когда мы добавляем букву в стек, это соответствует тому, что на стержень пирамидки сверху мы надеваем кольцо, на котором написана соответствующая буква. Когда берем букву из стека, то это соответствует тому, что мы снимаем со стержня верхнее кольцо, и смотрим, какая буква на нем написана.

Например, слово TROT в слово TORT может быть преобразовано анаграммером двумя различными последовательностями операций: 11112222 или 12112212.

Напишите программу, которая по двум заданным словам вычисляет количество различных последовательностей операций анаграммера, которые преобразуют первое из этих слов во второе.

Входные данные

Первая строка входного файла INPUT.TXT содержит исходное слово, а вторая — слово, которое необходимо получить. Слова состоят только из заглавных английских букв и имеют длину от 1 до 50 символов. Оба слова имеют одинаковую длину. В этих строках не содержится пробелов.

Выходные данные

В первой строке выходного файла OUTPUT.TXT должно содержаться количество последовательностей операций анаграммера, с помощью которых можно преобразовать первое слово во второе.

Примеры

INPUT.TXTOUTPUT.TXT
1TROT
TORT
2
2MADAM
ADAMM
4
3LONG
GONG
0
4AAAAAAAA
AAAAAAAA
1430

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

[Обсуждение] [Все попытки] [Лучшие попытки]

Красноярский краевой Дворец пионеров, (c)2006 - 2017, ICQ: 151483