Nổi Bật Trong Đàn

Điểm: 1,00 (OI)

Giới hạn thời gian: 4.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Farmer John muốn biết điều gì khiến mỗi con bò trong đàn của ông trở nên đặc biệt. Để đánh giá tính độc đáo của con bò thứ $i$ , ông đặt tên cho mỗi con bò một chuỗi ký tự $s_{i}$ và muốn đếm tổng số ký tự trong tất cả các xâu con (substring liên tiếp) của $s_{i}$ mà không xuất hiện như là xâu con trong bất kỳ chuỗi $s_{j}$ nào khác ( $j \neq i$ ).

Nói chính xác hơn, với mỗi con bò $i$ , hãy tính tổng độ dài của tất cả các xâu con phân biệt của $s_{i}$ mà không là xâu con của $s_{j}$ với mọi $j \neq i$ .

Dữ liệu vào

Dòng đầu tiên chứa số nguyên $N$ ( $1 \leq N \leq 10^{5}$ ).
$N$ dòng tiếp theo, dòng thứ $i$ chứa chuỗi $s_{i}$ — tên của con bò thứ $i$ , chỉ gồm các chữ cái thường.
Tổng độ dài của tất cả $N$ chuỗi không vượt quá $10^{5}$ .

Dữ liệu ra

In ra $N$ dòng, dòng thứ $i$ chứa một số nguyên — tổng độ dài các xâu con phân biệt của $s_{i}$ không xuất hiện trong bất kỳ chuỗi nào khác.

Ràng buộc

$1 \leq N \leq 10^{5}$
Tổng độ dài tất cả chuỗi $\leq 10^{5}$
Mỗi $s_{i}$ chỉ gồm chữ cái thường (a-z)

Ví dụ

Input	Output	Giải thích
3 amy tommy bessie	3 11 19	Với "amy": xâu con duy nhất không xuất hiện trong "tommy" hay "bessie" là "amy" (độ dài 3). Với "tommy": tổng độ dài là 11. Với "bessie": toàn bộ xâu con không xuất hiện ở đâu khác, tổng là 19.
3 aaabbb ababab aabbaa	7 7 7	Mỗi chuỗi có tổng độ dài các xâu con độc đáo bằng 7.

Ghi chú

Xâu con ở đây là substring liên tiếp (không phải subsequence).
Hai xâu con bằng nhau (dù ở vị trí khác nhau trong cùng một chuỗi) chỉ được tính một lần.
Nếu một con bò có tên là xâu con của chuỗi khác (e.g., "am" xuất hiện trong "tommy"), xâu đó không được tính.

Bình luận

Không có bình luận tại thời điểm này.