DFA

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

요약

유한 개의 단어로 이루어진 언어를 정확히 인식하는 DFA의 최소 상태 수를 구합니다.

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

문제

결정적 유한 오토마타(DFA)는 방향 간선을 가진 멀티그래프이다. 정점은 상태(state), 간선은 전이(transition)라고 부른다.

DFA의 모든 전이에는 글자 하나가 적혀 있다. 또한 각 상태 $s$ 와 각 글자 $l$ 에 대해, $s$ 에서 나가면서 글자 $l$ 이 적힌 전이는 최대 한 개만 존재한다.

DFA에는 시작 상태가 하나 있고, 최종 상태들의 집합(상태 전체의 부분집합)이 있다. DFA는 하나의 언어를 정의한다. 어떤 단어가 이 언어에 속하려면, 시작 상태에서 출발하여 어떤 최종 상태에 도달하는 경로가 있어야 하고, 그 경로의 간선에 적힌 글자들을 순서대로 이어 붙인 것이 그 단어와 같아야 한다.

단어의 개수가 유한한 언어가 주어지면, 이 언어를 정확히 인식하는 DFA를 항상 만들 수 있다. 예를 들어 언어 {fix, foo, ox}를 단순하게 나타낸 DFA는 상태가 7개이지만, 이는 상태 수가 가장 적은 DFA가 아니다. 같은 언어를 상태 5개로도 나타낼 수 있으며, 5개보다 적은 상태로는 이 언어를 나타낼 수 없다.

언어가 주어졌을 때, 이 언어를 인식하는 DFA를 만드는 데 필요한 상태의 최소 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 단어의 개수 $n$ 이 주어진다. ( $1 \le n \le 5000$ )

다음 $n$ 개의 줄에는 단어가 한 줄에 하나씩 주어진다. 각 단어는 알파벳 소문자로만 이루어져 있으며 길이는 최대 30이다. 입력으로 주어지는 모든 단어는 서로 다르다.

출력

첫째 줄에 주어진 언어를 인식하는 DFA를 만드는 데 필요한 상태의 최소 개수를 출력한다.

예제7

예제 1
입력
```
3
fix
foo
ox
```
예상 출력
```
5
```
예제 2
입력
```
1
a
```
예상 출력
```
2
```
예제 3
입력
```
1
abcde
```
예상 출력
```
6
```
예제 4
입력
```
2
ab
cb
```
예상 출력
```
3
```
예제 5
입력
```
2
ab
ac
```
예상 출력
```
3
```
예제 6
입력
```
2
a
ab
```
예상 출력
```
3
```
예제 7
입력
```
3
a
b
c
```
예상 출력
```
2
```