빈출 부분 문자열

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

요약

K개의 DNA 문자열이 주어질 때, i가 2부터 K까지인 각 경우에 대해 i개 이상의 문자열에 공통으로 나타나는 가장 긴 부분 문자열의 길이를 구합니다.

난이도: 보통10점 중 7점
유형: 문자열 매칭, 슬라이딩 윈도우, 정렬
정답자: 아직 제출이 없습니다

문제

우주생물학자가 행성 Alphabet의 생명체를 연구한다. 이 행성의 생명체는 DNA를 기반으로 하며, 뉴클레오타이드는 26종이다. 따라서 Alphabet 생명체의 DNA는 영문 소문자로 이루어진 문자열로 표현된다. 연구자는 K개 생명체의 DNA를 해독했다. 각 DNA 문자열은 서로 같을 수도 있으며, 전체 길이의 합은 N 뉴클레오타이드이다. 그녀는 이 생명체들 사이에서 자주 나타나는 DNA 가닥(부분 문자열)을 찾고자 한다. $2 \le i \le K$ 에 대해 $L(i)$ 는 최소 $i$ 개의 생명체에 공통으로 나타나는 연속된 뉴클레오타이드 가닥 중 가장 긴 것의 길이이다. $L(i)$ 는 0일 수 있다.

배열 $L$ 을 계산하라.

입력

첫 줄에 생명체의 수를 나타내는 정수 $K$ 가 주어진다. 이어지는 $K$ 줄에는 각각 빈 문자열이 아닌 영문 소문자 문자열이 주어진다.

출력

$L(2), L(3), \ldots, L(K)$ 의 값을 한 줄에 하나씩 $K-1$ 줄에 출력한다.

제한

$2 \le N \le 200{,}000$

$2 \le K \le N$

힌트

"atter"는 두 문자열에 나타난다.

"mat"는 세 문자열에 나타난다.

"ma"(또는 "at", "te")는 네 문자열에 나타난다.

"ma"는 다섯 문자열에 나타난다.

"a"는 모든 문자열에 나타난다.

예제1

예제 1

입력

6
matter
animate
pattern
thermal
domain
teammate

예상 출력