Задачи
Суффиксный поднабор
Суффиксный поднабор
Вам задан набор s_1, s_2, ..., s_n, состоящий из n строк.
Требуется найти такой поднабор этого набора, что выполняются два условия:
существует строка t, такая, что все строки поднабора являются ее суффиксами;
количество строк в поднаборе максимально.
Ваша задача вывести количество строк в таком поднаборе.
Входные данные
В первой строке записано целое число n (1 ≤ n ≤ 10^5) — количество строк в наборе. В каждой из последующих n строк записана строка. В i-той из них записана непустая строка s_i. Все строки состоят только из строчных латинских символов. Суммарная длина заданных строк не превосходит 10^5.
Выходные данные
Выведите единственное целое число — количество строк в описанном поднаборе.
Пример
Входные данные #1
6 bb bb b aaa aa z
Выходные данные #1
3