Pick a Pair

시간 제한1초메모리 제한1024 MB

요약

길이가 같은 단어 짝수 개가 주어질 때, 각 쌍이 공유하는 공통 접두사의 최소 길이를 최대로 만드는 값을 구한다.

난이도: 보통10점 중 6점
유형: 이분 탐색, 트라이, 그리디, 문자열 매칭
정답자: 아직 제출이 없습니다

문제

Friends play an interesting game with words. The goal of this game is arranging words in pairs.

Friends have $n$ words of the same length. They are choosing the largest number $k$ such that it is possible to divide the words into pairs so that words in each pair have common prefix of length at least $k$ .

Find the maximum possible value of $k$ .

입력

The first line of input contains an even integer $n$ --- number of words ( $1 \leq n \leq 2\cdot 10^5$ ).

The following $n$ lines contain words that the friends have. All words have same length. Total words length is less or equal to $2 \cdot 10^6$ .

출력

Output maximal possible value of $k$ .

예제2

예제 1
입력
```
4
aabc
aacc
bbbb
bbbd
```
예상 출력
```
2
```
예제 2
입력
```
2
a
b
```
예상 출력
```
0
```