Задача №1807. Древнее волшебство
Иван-царевич в глубокой печали: морской царь поручил ему перепахать до утра огромную пустошь на морском дне и засеять рожью. Понятно, что без волшебства тут не справиться! По счастью, дочь морского царя, Василиса Премудрая, предложила Ивану-царевичу свою помощь.
У Василисы в сундуке хранятся грамоты с древними заклинаниями. Она втайне была в учении у самой Бабы-Яги, поэтому знает, что, чтобы творить волшебство, нужно произнести заклинание, да такое, в котором скрыто содержится нужное волшебное слово. Но достаточно ли сильны заклинания, хранящиеся в сундуке?
Вот что Василиса Премудрая узнала от Бабы-Яги:
Вхождение слова в заклинание — это подпоследовательность букв заклинания, совпадающая со словом. Буквы слова могут идти не подряд, но должны быть расположены в том же порядке. К примеру, заклинания «cadabra» и «barabara» содержат слово «abra», а заклинание «raba» — не содержит.
Вхождение называют скрытым, если никакие две его буквы не идут подряд. Например, в заклинание «abuba» слово «aua» входит скрыто, так как буквы вхождения (первая, третья и пятая) идут не подряд, а через одну. В заклинание «bauab» слово «aua», напротив, входит не скрыто.
Силой заклинания относительно волшебного слова считается количество скрытых вхождений в него этого волшебного слова. Например, волшебное слово «az» в заклинание «abazaba» входит два раза, но только один раз — скрыто, поэтому сила его равна единице.
Василиса хочет посчитать силу заклинания, которое она достала из сундука. Да вот беда — заклинание длинное, вхождений много, а ещё нужно отличать скрытые вхождения от не скрытых...
Зная заклинание и волшебное слово, посчитайте силу этого заклинания относительно данного волшебного слова.
В первой строке входного файла задано заклинание. Во второй строке задано волшебное слово. Обе строки не пусты, состоят из маленьких букв латинского алфавита, а длина каждой из них не превосходит 45 символов.
В первой строке выходного файла выведите одно число — силу заклинания относительно данного волшебного слова.
В первом примере волшебное слово «az» входит в заклинание скрыто всего один раз: «a» соответствует первой букве заклинания, а «z» — четвёртой. Другое вхождение волшебного слова, в котором «a» соответствует третьей букве, а «z» — четвёртой, не является скрытым, так как соседние буквы волшебного слова расположены в заклинании рядом.
Во втором примере две буквы «i» могут поместиться, только если они соответствуют четвёртой и шестой буквам заклинания; буква «e», которая должна стоять перед ними, может соответствовать первой или второй букве заклинания.
abazaba az
1
eeeiiieee eii
2