Похожие имена
Как-то раз n друзей собрались сыграть в "Among us", но при этом они хотели, чтобы каждый человек, заходящий в лобби, понимал, что они играют вместе. Для этого они решили выбрать никнеймы с похожим началом, но поскольку каждому дорог его текущий никнейм, никто не хочет его сильно изменять.
В качестве компромисса было принято следующее решение: каждый игрок сдвинет свой никнейм по циклу на какое-то количество символов так, чтобы общий префикс никнеймов всех игроков был как можно длиннее. Циклическим сдвигом строки s = s[0]s[1]...s[n] называется строка вида s[i] = s[i]s[i+1]..s[n]s[0]s[1]...s[i−1], а префиксом - строка вида p[i] = s[0]s[1]...s[i].
Так вот, возвращаясь к никнеймам: решить эту задачу предстоит вам, потому что игроки - не программисты, и для них это слишком сложно. Помогите им найти максимальный общий префикс, который можно получить, сдвинув их никнеймы по циклу.
Входные данные
В первой строке задано число n (1 ≤ n ≤ 10^5) - количество игроков.
В следующих n строках заданы никнеймы игроков: на i-й строке дан никнейм i-го игрока s[i] (1 ≤ s[i] ≤ 10^5) - последовательность строчных латинских букв. Гарантируется, что сумма длин всех никнеймов не превосходит 10^5.
Выходные данные
Найдите длину наибольшего общего префикса, который могут получить игроки, применив к своим никнеймам какие-то циклические сдвиги.