E - Karuta Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 500500

問題文

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

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

  • x,yx, y の長さはいずれも nn 以上
  • 11 以上 nn 以下の全ての整数 ii に対し、xxii 文字目と yyii 文字目が等しい

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

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

制約

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

入力

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

NN
S1S_1
S2S_2
\vdots
SNS_N

出力

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


入力例 1Copy

Copy
3
abc
abb
aac

出力例 1Copy

Copy
2
2
1

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


入力例 2Copy

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

出力例 2Copy

Copy
4
3
2
1
0
1
0
4
3
2
1

Score : 500500 points

Problem Statement

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

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

  • The lengths of xx and yy are both at least nn.
  • For all integers ii between 11 and nn, inclusive, the ii-th character of xx and that of yy are equal.

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

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

Constraints

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

Input

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

NN
S1S_1
S2S_2
\vdots
SNS_N

Output

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


Sample Input 1Copy

Copy
3
abc
abb
aac

Sample Output 1Copy

Copy
2
2
1

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


Sample Input 2Copy

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

Sample Output 2Copy

Copy
4
3
2
1
0
1
0
4
3
2
1


2025-04-28 (Mon)
17:51:15 +00:00