문제
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을 만족한다.
예제1
입력
5
A
B
AA
BBB
AAA
출력
3
예제2
입력
5
A
ABA
BBB
ABABA
AAAAAB
출력
3
예제3
입력
6
A
B
C
D
A
B
출력
2
출처
COCI 2015/2016 contest2 4