접두사

면접 대비

시간 제한2초메모리 제한128 MB

요약

최대 50개의 단어가 주어질 때, 한 단어가 다른 단어의 접두사가 되지 않는 최대 부분집합의 크기를 트라이와 트리 DP로 구합니다.

난이도: 보통10점 중 5점
유형: 트라이, 동적 계획법, 트리, 문자열
정답자: 아직 제출이 없습니다

문제

어떤 단어 집합이 접두사 없는 집합이라는 것은, 그 집합 안의 어떤 단어도 같은 집합 안의 다른 단어의 접두사가 되지 않는다는 뜻이다. 예를 들어 {hello}, {hello, goodbye, giant, hi}, 그리고 빈 집합은 모두 접두사 없는 집합이다. 반면 {hello, hell}, {giant, gig, g}는 접두사 없는 집합이 아니다.

N개의 단어로 이루어진 모음이 주어진다. 이 단어들 중 일부를 골라 접두사 없는 집합을 만들 때, 고를 수 있는 단어 수의 최댓값을 구하시오.

입력

첫째 줄에 단어의 개수 N이 주어진다. N은 50 이하의 자연수이다.

둘째 줄부터 N개의 줄에 단어가 하나씩 주어진다. 각 단어는 알파벳 소문자로만 이루어져 있으며, 길이는 최대 50이다. 같은 단어가 두 번 이상 주어질 수 있다.

출력

첫째 줄에 정답을 출력한다.

예제4

예제 1
입력
```
6
hello
hi
h
run
rerun
running
```
예상 출력
```
4
```
예제 2
입력
```
6
a
b
cba
cbc
cbb
ccc
```
예상 출력
```
6
```
예제 3
입력
```
6
a
ab
abc
abcd
abcde
abcdef
```
예상 출력
```
1
```
예제 4
입력
```
3
topcoder
topcoder
topcoding
```
예상 출력
```
2
```