← 返回题目列表

AtCoder · abc287_e

H. 歌留田

中文机器翻译题面 查看原题

分数: 500 点

问题陈述

你被给予 N 由小写英文字母组成的字符串。 让 其中 S_i 是 i-th (i = 1, 2, \dots, N) 。

对于两个字符串 x 和 y, \mathrm{LCP}(x, y) 被定义为最大整数 n 满足以下所有条件:

  • 的长度 x 和 y 至少都是 n.
  • 对于所有整数 i 之间 1 和 n,包含在内, i- 第一个字符 x 以及 y 相等。

查找所有值的以下值 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-th (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