Задача N. Число кодонов в ДНК

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

Условие

Цепочка молекулы ДНК представляет собой последовательность из четырех разновидностей нуклеотидов,
для обозначения которых используются буквы латинского алфавита: A, C, G, T.

Тройки подряд идущих нуклеотидов образуют триплеты (кодоны), отвечающие за кодирование генетической информации.

Каждый кодон однозначно связан с какой-либо аминокислотой, входящей в состав живого организма.
Также известно, что соседние кодоны не перекрываются между собой.

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

Однако неизвестно, какая именно часть была утеряна, и с какого места начинается первый кодон.
При этом допускается один из возможных вариантов ее разрыва:

  1. первый кодон был записан полностью;
  2. от первого кодона осталось только два последних символа;
  3. от первого кодона остался только один символ.

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

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

Входной файл "input.txt" содержит заданную последовательность нуклеотидов.

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

Выходной файл "output.txt" должен содержать все найденные кодоны,
расположенные в лексикографическом порядке.

Напротив каждого кодона записываются три числа, указывающие
его количество в каждом из вариантов.

Ограничения

Длина исходной последовательности
не превосходит 107.

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

Входной файл (input.txt) Выходной файл (output.txt)
1
AGTAGTCATAGAGTCT
AGA 1 0 0
AGT 2 1 0
ATA 0 0 1
CAT 1 0 0
GAG 0 0 1
GTA 0 0 1
GTC 1 0 1
TAG 0 2 0
TCA 0 1 0
TCT 0 0 1
2
TA

0.143s 0.024s 15