题目描述

给定 $N$ 个由小写英文字母组成的字符串。第 $i$ 个字符串记为 $S_i$。

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

• $x, y$ 的长度都不少于 $n$。
• 对于所有 $1 \leq i \leq n$，$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$ 行输出 $\displaystyle\max\_{i \neq j} \mathrm{LCP}(S\_i, S\_j)$。

样例 1

输入

3
abc
abb
aac

输出

2
2
1

样例 2

输入

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$

样例解释 1

$\mathrm{LCP}(S\_1, S\_2) = 2,\ \mathrm{LCP}(S\_1, S\_3) = 1,\ \mathrm{LCP}(S\_2, S\_3) = 1$。

由 ChatGPT 4.1 翻译