Karuta

题目描述

给出 $N$ 个由小写英文字母组成的字符串。令 $S_i$ 为第 $i$ 个字符串 $(i = 1, 2, \dots, N)$。 对于两个字符串 $x$ 和 $y$，$\mathrm{LCP}(x, y)$ 定义为满足下列所有条件的最大整数 $n$：

$x$ 和 $y$ 的长度都至少为 $n$。 对于所有整数 $i$ 在 $1$ 到 $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$ 行 $(i = 1, 2, \dots, N)$ 应包含 $\displaystyle \max_{i \neq j} \mathrm{LCP}(S_i, S_j)$。

3
abc
abb
aac

2
2
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$。$\mathrm{LCP}(S_1, S_2) = 2, \mathrm{LCP}(S_1, S_3) = 1$, and $\mathrm{LCP}(S_2, S_3) = 1$.

标签: AtCoder|abc287E

来源

AtCoder|abc287E