비밀번호

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

요약

여러 비밀번호 중 한 문자열이 다른 문자열의 부분 문자열인 서로 다른 두 사용자의 순서쌍 개수를 구한다.

난이도: 보통10점 중 5점
유형: 문자열 매칭, 해시맵, 트라이
정답자: 아직 제출이 없습니다

문제

인기 소셜 네트워크 Secret Network에서 사용자 정보가 유출됐다. 유출된 자료에는 모든 사용자의 비밀번호가 들어 있다.

컴퓨터 보안을 공부하던 학생 미하엘은 이 사건에 흥미를 느꼈다. 소셜 네트워크를 이리저리 만져 보던 중 또 다른 허점을 찾아냈다. 실제 비밀번호와 같은 부분 문자열을 포함하는 문자열을 입력하면 로그인에 성공한다는 것이다. 예를 들어 비밀번호가 abc인 사용자는 abc, abcd, imaabcnema 중 무엇을 입력해도 로그인에 성공하지만, axbc를 입력하면 실패한다.

미하엘은 서로 다른 두 사용자의 순서쌍 가운데, 첫 번째 사용자가 자신의 비밀번호를 그대로 입력해 두 번째 사용자로 로그인할 수 있는 순서쌍이 몇 개인지 알고 싶다.

입력

첫째 줄에 사용자의 수 $N$ ( $1 \le N \le 20000$ )이 주어진다. 다음 $N$ 개의 줄에 사용자의 비밀번호가 한 줄에 하나씩 주어진다. 비밀번호는 길이가 1 이상 10 이하인 영어 소문자 문자열이다.

출력

문제에서 설명한 순서쌍의 개수를 첫째 줄에 출력한다.

설명

세 사용자의 비밀번호가 차례로 x, x, xy인 경우를 보자. 첫 번째 사용자는 두 번째 사용자로, 두 번째 사용자는 첫 번째 사용자로 로그인할 수 있다. 세 번째 사용자는 첫 번째 사용자로도, 두 번째 사용자로도 로그인할 수 있다. 따라서 답은 4다.

예제3

예제 1
입력
```
3
aaa
aa
abb
```
예상 출력
```
1
```
예제 2
입력
```
3
x
x
xy
```
예상 출력
```
4
```
예제 3
입력
```
5
mir
mirta
ta
ir
t
```
예상 출력
```
6
```