#PU768. USACO 2017 December Contest, Platinum — Problem 1. Standing Out from the Herd

    ID: 1252 传统题 文件IO:standingout 2000ms 256MiB 尝试: 0 已通过: 0 难度: 省选/NOI- 上传者: 标签>USACO赛事:dec17来源:usaco.orgscoring:equal_test_cases字符串哈希

USACO 2017 December Contest, Platinum — Problem 1. Standing Out from the Herd

USACO 2017 December Contest, Platinum — Problem 1. Standing Out from the Herd

题目描述

Just like humans, cows often appreciate feeling they are unique in some way. Since Farmer John's cows all come from the same breed and look quite similar, they want to measure uniqueness in their names. Each cow's name has some number of substrings. For example, "amy" has substrings {a, m, y, am, my, amy}, and "tommy" would have the following substrings: {t, o, m, y, to, om, mm, my, tom, omm, mmy, tomm, ommy, tommy}. A cow name has a "uniqueness factor" which is the number of substrings of that name not shared with any other cow. For example, If amy was in a herd by herself, her uniqueness factor would be 6. If tommy was in a herd by himself, his uniqueness factor would be 14. If they were in a herd together, however, amy's uniqueness factor would be 3 and tommy's would be 11. Given a herd of cows, please determine each cow's uniqueness factor.

输入格式

The first line of input will contain NN (1≤N≤1051 \le N \le 10^5). The following NN lines will each contain the name of a cow in the herd. Each name will contain only lowercase characters a-z. The total length of all names will not exceed 10510^5.

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

3
amy
tommy
bessie
3
11
19
Problem credits: Matt Fontaine