Схожі імена#11082

Схожі імена

1 секунда

128 мегабайтів

Складна

Якось $n$ друзів зібралися пограти в "Among us", але вони хотіли, щоб кожен, хто заходить у лобі, розумів, що вони грають разом. Для цього вони вирішили вибрати нікнейми з подібним початком, але оскільки кожному дорогий його поточний нікнейм, ніхто не хоче його сильно змінювати.

Як компроміс було прийнято таке рішення: кожен гравець зрушить свій нікнейм по циклу на певну кількість символів так, щоб спільний префікс нікнеймів усіх гравців був якомога довшим. Циклічним зсувом рядка $s = s_{0} s_{1} \dots s_{n}$ s = s_0 s_1 \ldots s_n називається рядок виду $s_{i} = s_{i} s_{i + 1} \dots s_{n} s_{0} s_{1} \dots s_{i - 1}$ s_i = s_i s_{i+1} \ldots s_n s_0 s_1 \ldots s_{i-1}, а префіксом - рядок виду $p_{i} = s_{0} s_{1} \dots s_{i}$ p_i = s_0 s_1 \ldots s_i.

Отже, повертаючись до нікнеймів: вирішити цю задачу належить вам, тому що гравці - не програмісти, і для них це занадто складно. Допоможіть їм знайти максимальний спільний префікс, який можна отримати, зсунувши їх нікнейми по циклу.

Вхідні дані

У першому рядку задано число $n$ ( $1 \leq n \leq 1 0^{5}$ 1 \leq n \leq 10^5) - кількість гравців.

У наступних $n$ рядках задано нікнейми гравців: у $i$ -му рядку дано нікнейм $i$ -го гравця $s_{i}$ s_i ( $1 \leq ∣ s_{i} ∣ \leq 1 0^{5}$ 1 \leq |s_i| \leq 10^5) - послідовність малих латинських літер. Гарантується, що сума довжин усіх нікнеймів не перевищує $1 0^{5}$ 10^5.

Вихідні дані

Знайдіть довжину найбільшого спільного префікса, який можуть отримати гравці, застосувавши до своїх нікнеймів якісь циклічні зсуви.

Приклади

Приклад 1

Приклад 2