Tekstide erinevus

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

요약

N개의 문자열이 주어질 때, 각 문자열을 다른 모든 문자열로 바꾸는 데 필요한 끝에 추가하기와 마지막 글자 지우기 연산 횟수의 합을 모든 순서쌍에 대해 구한다.

난이도: 보통10점 중 6점
유형: 트라이, 문자열, 누적 합, 정렬
정답자: 아직 제출이 없습니다

문제

Kuulus tarkvarafirma Interplanetary Software Systems on loomas uut tekstitoimetit, mis suudab töödelda väga pikki väikestest ladina tähtedest koosnevaid ridu. Toote esimesel versioonil on ainult kaks funktsiooni:

tähe lisamine rea lõppu;
rea viimase tähe kustutamine (kui rida ei ole tühi).

Nimetame kahe sõne $s$ ja $t$ erinevuseks $\mathrm{diff}(s, t)$ minimaalset sõnest $s$ sõne $t$ saamiseks vajalike käskude arvu. Näiteks $\mathrm{diff}($ 'tests','text' $) = 5$ : algul kustutame sõne 'tests' lõpust kolm viimast tähte ja seejärel lisame tulemuse lõppu tähed 'x' ja 't'.

Kirjutada programm, mis antud $N$ sõne $S\_i$ kohta leiab $\mathrm{diff}(S\_i, S\_j)$ summa üle kõigi paaride, kus $1 \le i \le N$ ja $1 \le j \le N$ .

입력

Faili esimesel real on tekstiridade arv $N$ ( $1 \le N \le 200\\,000$ ) ja järgmisel $N$ real igaühel üks väikestest ladina tähtedest koosnev mittetühi sõne $S\_i$ . On teada, et $S\_i$ pikkuste summa ei ületa $10^6$ .

출력

Faili ainsale reale väljastada otsitav erinevuste summa.

예제2

예제 1
입력
```
3
a
ab
aaaaa
```
예상 출력
```
20
```
예제 2
입력
```
4
b
aab
baaa
ba
```
예상 출력
```
44
```