28644번 - Похожие имена 다국어

Как-то раз $n$ друзей собрались сыграть в <<Among us>>, но при этом они хотели, чтобы каждый человек, заходящий в лобби, понимал, что они играют вместе. Для этого они решили выбрать никнеймы с похожим началом, но поскольку каждому дорог его текущий никнейм, никто не хочет его сильно изменять.

В качестве компромисса было принято следующее решение: каждый игрок сдвинет свой никнейм по циклу на какое-то количество символов так, чтобы общий префикс никнеймов всех игроков был как можно длиннее. Циклическим сдвигом строки $s = s_0 s_1 \ldots s_n$ называется строка вида $s^i = s_i s_{i+1} \ldots s_n s_0 s_1 \ldots s_{i - 1}$, а префиксом --- строка вида $p^i = s_0 s_1 \ldots s_i$.

Так вот, возвращаясь к никнеймам: решить эту задачу предстоит вам, потому что игроки --- не программисты, и для них это слишком сложно. Помогите им найти максимальный общий префикс, который можно получить, сдвинув их никнеймы по циклу.

В первой строке задано число $n$ --- количество игроков ($1 \leqslant n \leqslant 10^5$).

В следующих $n$ строках заданы никнеймы игроков: на $i$-й строке дан никнейм $i$-го игрока $s_i$ --- последовательность строчных латинских букв ($1 \leqslant |s_i| \leqslant 10^5$). Гарантируется, что сумма длин всех никнеймов не превосходит $10^5$.

Найдите длину наибольшего общего префикса, который могут получить игроки, применив к своим никнеймам какие-то циклические сдвиги.