Похожие имена
Похожие имена
Как-то раз n друзей собрались сыграть в "Among us", но при этом они хотели, чтобы каждый человек, заходящий в лобби, понимал, что они играют вместе. Для этого они решили выбрать никнеймы с похожим началом, но поскольку каждому дорог его текущий никнейм, никто не хочет его сильно изменять.
В качестве компромисса было принято следующее решение: каждый игрок сдвинет свой никнейм по циклу на какое-то количество символов так, чтобы общий префикс никнеймов всех игроков был как можно длиннее. Циклическим сдвигом строки s = s0s1...sn
называется строка вида si
= sisi+1..sns0s1...si−1
, а префиксом - строка вида pi
= s0s1...si
.
Так вот, возвращаясь к никнеймам: решить эту задачу предстоит вам, потому что игроки - не программисты, и для них это слишком сложно. Помогите им найти максимальный общий префикс, который можно получить, сдвинув их никнеймы по циклу.
Входные данные
В первой строке задано число n (1 ≤ n ≤ 105
) - количество игроков.
В следующих n строках заданы никнеймы игроков: на i-й строке дан никнейм i-го игрока si
(1 ≤ si
≤ 105
) - последовательность строчных латинских букв. Гарантируется, что сумма длин всех никнеймов не превосходит 105
.
Выходные данные
Найдите длину наибольшего общего префикса, который могут получить игроки, применив к своим никнеймам какие-то циклические сдвиги.
4 abacada abracadabra rxacadd dzzzaca
4
2 abacaba acabaab
7