Фермер Джон исследует последовательности DNA (ДНК) на своей
призово-удойной корове Бесси. DNA-последовательности - это упорядоченные
списки строк, содержащих одну или более букв 'A', 'C', 'G', 'T'.
Как обычно для DNA-последовательностей, результат - это множество
строк, которые являются последовательными фрагментами DNA. Пара строк,
например, 'GATTA' и 'TACA' наиболее вероятно представляют строку
'GATTACA' - перекрывающиеся символы сливаются, поскольку они
имеют вероятность дуплицироваться во время получения. В общем случае
слияние пары строк обеспечивает удаление наибольшего перекрытия во время
их конкатенации. Заметим, что имеется ввиду перекрытие конца одной строки
и начала другой строки, а не середины строк. Строка 'GATTACA' перекрывает
строку 'TTACA' полностью, в то время как строки 'GATTACA' и 'TTA' совсем
не пересекаются.
Вам дано N (2 <= N <= 100) DNA-последовательностей, все имеют длину
от 1 до 50. Найдите и выведите длину наибольшего перекрытия между
произвольной парой строк.
PROBLEM NAME: dna
Формат ввода:
* Строка 1: Одно целое число N
* Строки 2..N+1: Какждая строка содержит одну DNA-последовательность.
Пример ввода (файл dna.in):
4
CGCCAC
TGTCGC
GAATGA
GAGGCGA
Пояснения к вводу:
Четыре строки; в трех длина 6 символов, в одной 7.
Формат вывода:
* Строка 1: Одно целое число - длина наибольшего перекрытия между
произвольной парой строк (в любом порядке).
Пример вывода (файл dna.out):
3
Пояснения к выводу:
CGC является началом первой строки и концом второй:
CGCCAC
TGTCGC
поэтому наибольшее перекрытие 3