Standing Out from the Herd

题目描述

就像人类一样，奶牛也常常希望自己在某些方面是独一无二的。 由于 Farmer John 的奶牛都来自同一品种，外观十分相似，她们想通过名字来衡量独特性。

每头奶牛的名字都有若干个子串。例如，“amy”的子串有 {a, m, y, am, my, amy}；而“tommy”的子串有：{t, o, m, y, to, om, mm, my, tom, omm, mmy, tomm, ommy, tommy}。

一个奶牛名字的“独特性因子（uniqueness factor）”定义为：该名字中不与任何其他奶牛共享的子串数量。 例如，如果 amy 单独在一个牛群中，她的独特性因子为 6；如果 tommy 单独在一个牛群中，他的独特性因子为 14。 但如果她们在同一个牛群中，amy 的独特性因子将为 3，而 tommy 的将为 11。

给定一个奶牛群，请计算每头奶牛的独特性因子。

输入格式

第一行输入包含 $N$（$1 \le N \le 10^5$）。接下来的 $N$ 行每行包含牛群中一头奶牛的名字。每个名字仅包含小写字母 a-z。所有名字的总长度不超过 $10^5$。

输出格式

输出 $N$ 个数字，每行一个，表示每头奶牛的独特性因子。

3
amy
tommy
bessie

3
11
19

提示

题目致谢：Matt Fontaine

标签: USACO|2017|Platinum

来源

USACO|2017|Platinum