ЛШ олимпиада 2008 - Перестановки с подстрокой

Задача A. Перестановки с подстрокой ≡

задачи
видимые пробелы
простые формулы
широкий текст
редактор

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

Условие

Даны строки S и P, состоящие из малых латинских букв. Требуется определить сколько различных слов, составленных из букв строки S, содержат в себе подстроку P.

Например, если S = dcba, P = bc, то получится 11 строк: bc, abc, bca, dbc, bcd, adbc, dabc, abcd, dbca, bcad, bcda.

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

Первая строка содержит строку S, вторая — строку P.

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

В выходном файле должно содержаться единственное число — количество слов.

Ограничения

Длины строк находятся в диапазоне от 1 до 12 букв. Все буквы строки S различны.

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

№	Входной файл (`input.txt`)	Выходной файл (`output.txt`)
1	`dbca bc`	`11`
2	`xyz xx`	`0`

Разбор

Сначала следует убедиться, что все буквы в строке P различны и содержатся в строке S. Если это условие не выполнено, вывести ответ 0 и завершить работу.

Далее рассмотрим все слова, получаемые из строки S и не содержащие символов из P. Если длина S равна N символам, а длина P — M символам, то количество таких слов длиной i (i = 0… N − M) составит (N − M)! / (N − M − i)!. В каждом слове имеется i + 1 позиция, куда можно вставить строку P. Просуммировав по i, получим ответ.