E - Karuta Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 500 点

問題文

英小文字からなる文字列が N 個与えられます。i \, (i = 1, 2, \dots, N) 番目のものを S_i と表します。

二つの文字列 x, y に対し、以下の条件を全て満たす最大の整数 n を \mathrm{LCP}(x, y) と表します。

  • x, y の長さはいずれも n 以上
  • 1 以上 n 以下の全ての整数 i に対し、x の i 文字目と y の i 文字目が等しい

全ての i = 1, 2, \dots, N に対し、以下の値を求めてください。

  • \displaystyle \max_{i \neq j} \mathrm{LCP}(S_i, S_j)

制約

  • 2 \leq N \leq 5 \times 10^5
  • N は整数
  • S_i は英小文字からなる長さ 1 以上の文字列 (i = 1, 2, \dots, N)
  • S_i の長さの総和は 5 \times 10^5 以下

入力

入力は以下の形式で標準入力から与えられる。

N
S_1
S_2
\vdots
S_N

出力

N 行出力せよ。i \, (i = 1, 2, \dots, N) 行目には、\displaystyle \max_{i \neq j} \mathrm{LCP}(S_i, S_j) を出力せよ。

入力例 1

3
abc
abb
aac

出力例 1

2
2
1

\mathrm{LCP}(S_1, S_2) = 2, \mathrm{LCP}(S_1, S_3) = 1, \mathrm{LCP}(S_2, S_3) = 1 です。

入力例 2

11
abracadabra
bracadabra
racadabra
acadabra
cadabra
adabra
dabra
abra
bra
ra
a

出力例 2

4
3
2
1
0
1
0
4
3
2
1

Score : 500 points

Problem Statement

You are given N strings consisting of lowercase English letters. Let S_i be the i-th (i = 1, 2, \dots, N) of them.

For two strings x and y, \mathrm{LCP}(x, y) is defined to be the maximum integer n that satisfies all of the following conditions:

  • The lengths of x and y are both at least n.
  • For all integers i between 1 and n, inclusive, the i-th character of x and that of y are equal.

Find the following value for all i = 1, 2, \dots, N:

  • \displaystyle \max_{i \neq j} \mathrm{LCP}(S_i, S_j)

Constraints

  • 2 \leq N \leq 5 \times 10^5
  • N is an integer.
  • S_i is a string of length at least 1 consisting of lowercase English letters (i = 1, 2, \dots, N).
  • The sum of lengths of S_i is at most 5 \times 10^5.

Input

The input is given from Standard Input in the following format:

N
S_1
S_2
\vdots
S_N

Output

Print N lines. The i-th (i = 1, 2, \dots, N) line should contain \displaystyle \max_{i \neq j} \mathrm{LCP}(S_i, S_j).

Sample Input 1

3
abc
abb
aac

Sample Output 1

2
2
1

\mathrm{LCP}(S_1, S_2) = 2, \mathrm{LCP}(S_1, S_3) = 1, and \mathrm{LCP}(S_2, S_3) = 1.

Sample Input 2

11
abracadabra
bracadabra
racadabra
acadabra
cadabra
adabra
dabra
abra
bra
ra
a

Sample Output 2

4
3
2
1
0
1
0
4
3
2
1