0291. Криптография

Имя входного файла:	pair.in
Имя выходного файла:	pair.out
Ограничение по времени:	2 s
Ограничение по памяти:	256 megabytes

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

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

Проведя много часов за поиском этого ключа, Вовочка наконец узнал, как его определить. Оказалось, что ключ – это количество раз, которое первые два символа зашифрованного текста встречаются далее в этом тексте подряд.

Поиски ключа так измотали нашего героя, что он просит Вас помочь ему справиться с этой несложной задачей!

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

В первой строке входного файла находятся первые два символа зашифрованной строки. Во второй строке находится остаток зашифрованного текста длиной N символов (1 ≤ N ≤ 10⁵). В конце второй строки обязательно присутствует символ перевода строки. Все символы в строках – строчные и прописные символы латинского алфавита, а также цифры.

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

В выходной файл выведите одно целое число – количество раз, которое два символа из первой строки входного файла встречаются во второй строке входного файла подряд.

Пример:

pair.in	pair.out
ab cdef0	0
ab 1Rabab2Z	2
xx JiMxxxMDg3OyxxxYjMTA4xx	5

В первом примере пара символов "ab" ни разу не встречается в оставшейся строке, потому ответ равен нулю.

Во втором примере пара "ab" встречается в остатке текста начиная с 3 и 5 позиций.

В третьем примере пара "xx" встречается пять раз --- на 4, 5, 13, 14 и 22 позициях.

Источник: Первенство ПетрГУ. Сентябрь 2012.

Обсудить       Отправить решение



Версия для печати