Страница: 1 Отображать по:
#113555
Генерал Хенрик
  
Источники: [ Личные олимпиады, COCI, COCI 2015-2016, Раунд 2, Генерал Хенрик ]
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Известно, что в солнечной системе есть 8 планет и один планетоид. Мало кто знает, что ещё есть секретная планета, населенная медведями. Именно туда ассоциация Savez отправляет бравого генерала Хенрика для изучения медведей. Выяснилось, что медведи умеют телепортироваться. Расчётливый генерал Хедрик решил завербовать их в свою армию.

У одного медведя есть N строк (обозначим i -ю из них x i ). Исследования показывают, что количество раз, которое может телепортироваться медведь равно длине наибольшей подпоследовательности этих строк, удовлетворяющей такому правилу: строки x i и x j ( i < j ) могут принадлежать одной такой последовательности, если x i является и префиксом, и суффиксом x j .

Помогите уставшему от долгого полёта генералу Хендрику определить, сколько телепортаций сможет сделать данный медведь.

Входные данные

В первой строке содержится одно целое число N – количество строк, которые есть у медведя. В последующих N строках содержатся сами эти строки. Входной файл содержит не более двух миллионов символов.

Выходные данные

Выведите одно число – ответ на вопрос любопытного генерала Хендрика.

Примечание

В первом примере наибольшая последовательность A -> AA -> AAA В третьем примере наибольшая последовательность A -> A -> A или B -> B -> B

Примеры
Входные данные
5
A
B
AA
BBB
AAA
Выходные данные
3
Входные данные
5
A
ABA
BBB
ABABA
AAAAAB
Выходные данные
3
Входные данные
6
A
B
A
B
A
B
Выходные данные
3
Страница: 1 Отображать по:
Выбрано
:
Отменить
|
Добавить в контест