Молекулы ДНК отвечают в природе за передачу наследственной информации. Строение ДНК простое и сложное одновременно – её молекулы являются двумя длинными полимерными нитями, скрепленными между собой в двойную спираль. Каждая нить ДНК строится на основании всего 4 нуклеотидов: Аденина (A – Adenine), Гуанина (G – Guanine), Тимина (T – Thymine) и Цитозина (C – Cytosine). Нуклеотиды принято кодировать заглавными латинскими буквами и записывать их последовательность в виде строчки. Например, так: «ACTG».

В одной нити нуклеотиды соединяются последовательно в любом порядке, а вот вторая нить спирали строится строго на принципе комплиментарности: Аденин всегда образует пару с Тимином (A–T или T–A), а Цитозин с Гуанином (C–G или G–C). То есть, нуклеотид, находящийся на определенном месте первой нити, однозначно задает нуклеотид, находящийся на том же месте второй нити.

Например, если одна нить состоит из нуклеотидов «ACTGTAC», то вторая будет иметь вид «TGACATG».

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

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