E - Karuta

得分：500分

问题描述

你得到了N个由小写英文字母组成的字符串，记第i个字符串为$S_i$ (i = 1, 2, ..., N)。

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

• $x$和$y$的长度都至少为$n$。
• 对于所有整数$i$，满足$1 \leq i \leq n$，$x$的第$i$个字符和$y$的第$i$个字符相等。

找到对于所有$i = 1, 2, ..., 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, ..., N)$。
• $S_i$的长度之和至多为$5 \times 10^5$。

输入

输入数据从标准输入中按以下格式给出：

$N$

$S_1$

$S_2$

$\vdots$

$S_N$

输出

输出$N$行。第$i$行$(i = 1, 2, ..., N)$应该输出$\displaystyle \max_{i \neq j} \mathrm{LCP}(S_i, S_j)$。

3
abc
abb
aac

2
2
1

$\mathrm{LCP}(S_1, S_2) = 2, \mathrm{LCP}(S_1, S_3) = 1$，且$\mathrm{LCP}(S_2, S_3) = 1$。

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

4
3
2
1
0
1
0
4
3
2
1