COCI 2015/2016 contest2 4- 최장 부분 접두미사 수열(SAVEZ) > 문제은행 : 정보올림피아드&알고리즘




2974 : 최장 부분 접두미사 수열(SAVEZ)

제한시간
1000 ms   
메모리제한
64 MB   
해결횟수
2 회   
시도횟수
10 회   

문제

N개의 문자열로 이루어진 수열이 있다. 

당신은 이 수열에서 몇 개의 문자열을 선택해서 새로운 부분수열을 만들려고 한다. (이때 순서는 바뀌지 않는다.) 

한편, 이 부분수열의 모든 인접한 두 문자열의 쌍에 대 해서 앞의 문자열이 뒤의 문자열의 접두미사가 되어야 한다.

 

여기서, 한 문자열 A가 다른 문자열 B의 접두미사(Presuffix)가 된다는 말은 A가 B의 앞에서도 등장하고 뒤에서도 등장한다는 소리이다. 

예를 들어 KY는 KYUNKY의 접두미사이지만 NA는 BANANA의 접두미사가 아니다.

 

예를 들어, 수열 (A, B, AAA, BB, AA)이 있다면 (A, AA, AAA)는 앞서 언급한 수열의 부분수열이 아니다. 

한편, (A, B, BB)는 앞서 언급한 수열의 부분수열이지만 A가 B의 접두미사가 아니므로 조건을 만족하지 않는다. 

(A, B, AAA, BB, AA)의 부분 접두미사 수열​로 가능한 예로는 (A, AAA), (B, BB) 등이 있다.

 

N개의 문자열들의 수열이 주어질 때 이 수열의 부분수열 중 앞서 말한 조건을 만족하는 수열의 최대 길이를 출력하는 프로그램을 작성하여라.


입력형식

첫 번째 줄에는 N이 주어진다. (1 ≤ N ≤ 2,000,000) 두 번째 줄부터 N개의 줄에는 알파벳 대문자로 이루어진 문자열이 주어진다. N개의 문자열의 길이의 합은 2,000,000을 넘지 않는다.

출력형식

첫 번째 줄에 최장 부분 접두미사 수열의 길이를 출력한다. 채점 전체 데이터의 40%는 N ≤ 500을 만족한다.

입력 예

5 
A 
B 
AA 
BBB 
AAA

출력 예

3

입력 예

5 
A 
ABA 
BBB 
ABABA 
AAAAAB

출력 예

3

입력 예

6 
A 
B 
C 
D 
A 
B

출력 예

2


경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP