무리에서 돋보이기

사람과 마찬가지로, 소들도 자신이 어떤 면에서 특별하다고 느끼는 것을 좋아한다. 농부 존의 소들은 모두 같은 품종이고 생김새가 꽤 비슷하기 때문에, 소들은 이름으로 고유함을 측정하고 싶어한다.

각 소의 이름에는 여러 부분 문자열이 있다. 예를 들어 "amy"의 부분 문자열은 {a, m, y, am, my, amy}이고, "tommy"의 부분 문자열은 {t, o, m, y, to, om, mm, my, tom, omm, mmy, tomm, ommy, tommy}이다.

소 이름의 "고유도"는 그 이름의 부분 문자열 중 다른 어떤 소와도 공유하지 않는 것의 개수이다. 예를 들어 amy 혼자 무리에 있다면 고유도는 6이다. tommy 혼자 무리에 있다면 고유도는 14이다. 하지만 둘이 같은 무리에 있다면, amy의 고유도는 3이고 tommy의 고유도는 11이다.

소들의 무리가 주어질 때, 각 소의 고유도를 구하라.

Problem credits: Matt Fontaine

Problem credits: Matt Fontaine

입력의 첫째 줄에 \(N\) (\(1 \le N \le 10^5\))이 주어진다. 다음 \(N\)개의 줄에 무리에 속한 소의 이름이 하나씩 주어진다. 각 이름은 영어 소문자 a-z로만 이루어져 있다. 모든 이름의 총 길이는 \(10^5\)를 넘지 않는다.

\(N\)개의 수를 한 줄에 하나씩 출력하며, 각 소의 고유도를 나타낸다.

riseoj 작성

출처 올림피아드 > USACO > 2017-2018 > December > Platinum