Karuta

题目描述

给定 $N$ 个由小写英文字母组成的字符串,其中第 $i$ 个记为 $S_i$ ($i = 1, 2, \dots, N$)。

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

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

对每个 $i = 1, 2, \dots, N$,求:

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

输入格式

输入按以下格式从标准输入给出:

$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)$。

样例

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

数据范围

• $2 \leq N \leq 5 \times 10^5$
• $N$ 是整数。
• $S_i$ 是由小写英文字母组成的长度至少为 $1$ 的字符串 ($i = 1, 2, \dots, N$)。
• $S_i$ 的长度总和不超过 $5 \times 10^5$。