Задача G. Имя, сестра, имя!
Задачу добавил: alef
Успешно сдано решений: 18
— Кеша... — неуверенно позвала его коллега Ира за соседним столом, — назови, пожалуйста, какое-нибудь слово, начинающееся на «про»...— «Проверка» подойдет? — отозвался Кеша.
— Нет. Это слово я уже пробовала, не подходит, — вздохнула Ира.
Как выяснилось, Ира забыла пароль от архива. «И ведь я была уверена, что забыть такой пароль нельзя! — сокрушалась она. — А теперь — ну никаких воспоминаний. Честно говоря, я уже и не уверена, что он на «про» начинался».
«Пространство», «простокваша», «проволока», «простыня», «променад», «произношение» и даже «прожектор» не подходили.
Из дальнейших расспросов Кеша узнал, что пароль «придумался», когда Ира читала книгу — понравилось ей слово... А может, словосочетание или даже буквосочетание показалось забавным и запоминающимся.
Ваша задача — по заданному началу пароля и тексту, в котором пароль встречается, определить количество возможных паролей, если известно, что длина пароля не менее L1 и не более L2 символов.
Ради простоты будем считать, что все буквы в тексте латинские строчные, знаки препинания из него удалены и слова разделены только пробелами.
Возможный пароль составляется только из букв, пробелы в пароль не входят и не учитываются. Начало пароля не обязано совпадать с началом слова.
Формат входного файла input.txt
Первая строка — целые числа B, L1, L2, T через пробел. B — длина буквосочетания, которое помнит Ира, L1 — минимально возможная длина пароля, L2 — максимально возможная длина пароля, T — количество строк в тексте (2 < B <=L1 < L2; B <= 10; L1 < L2 <= 20; 1 <= T <= 500)
Вторая строка содержит B символов — буквосочетание, которое помнит Ира
Следующие T строк содержат текст, состоящий из маленьких латинских букв и пробелов.
Формат выходного файла output.txt
Первая строка — целое число — количество возможных паролей, подходящих по длине и начинающихся с указанного буквосочетания.
Пример входного файла
3 5 9 9
pro
prochitayte nebolshoy tekst pro programmirovanie na
yazyke prolog odnoy iz ego zadach yavlyaetsya proektirovanie
baz znaniy neprohodyaschiy interes k prologu
sprovotsirovan ego orientaciey na sistemy iskusstvennogo intellekta
v nekotorye dialekty yazyka prolog v nastoyaschee vremya probuyut
vkljuchit elementy imperativnogo programmirovaniya
kak i prochie decklarativnye yazyki on osnovan na sopostavlenii
utverzhdeniy s obrazcom chto uproschaet semantiku
yazyk lisp rozhdenny srazu posle fortrana v proshlom
Пример выходного файла
63