문제
사람과 비슷하게, 소들은 가끔 그들이 어떤 방식으로든 특별하기를 원한다. 때문에 농부 존의 소들은 모두 같은 품종이고 비슷하게 생겼지만, 그들은 이름에서 독창성을 가지기를 원한다.
모든 소들의 이름은 몇몇의 부분문자열을 가지고 있다. 예를 들어, “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이다.
무리에 속한 소들의 이름이 주어졌을 때, 각 소들에 대한 독창성 점수를 구하여라.
입력
첫 번째 줄에는 소의 마리수를 의미하는 자연수 N이 주어진다. (1 ≤ N ≤ 100,000)
다음 N개의 줄에는 각 소의 이름이 알파벳 소문자로 이루어진 문자열로 주어진다. 모든 이름의 길이 합은 105를 넘지 않는다.
출력
N개의 줄에, 각 소에 대한 독창성 점수를 한 줄에 하나씩 출력한다.
예제
3
amy
tommy
bessie
3
11
19
태그
출처
USACO 2017 December Platinum
로그인해야 코드를 작성할 수 있어요.