102874: [AtCoder]ABC287 E - Karuta

Problem Statement

You are given $N$ strings consisting of lowercase English letters. Let $S_i$ be the $i$-th $(i = 1, 2, \dots, N)$ of them.

For two strings $x$ and $y$, $\mathrm{LCP}(x, y)$ is defined to be the maximum integer $n$ that satisfies all of the following conditions:

• The lengths of $x$ and $y$ are both at least $n$.
• For all integers $i$ between $1$ and $n$, inclusive, the $i$-th character of $x$ and that of $y$ are equal.

Find the following value for all $i = 1, 2, \dots, N$:

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

Constraints

• $2 \leq N \leq 5 \times 10^5$
• $N$ is an integer.
• $S_i$ is a string of length at least $1$ consisting of lowercase English letters $(i = 1, 2, \dots, N)$.
• The sum of lengths of $S_i$ is at most $5 \times 10^5$.

Input

The input is given from Standard Input in the following format:

$N$
$S_1$
$S_2$
$\vdots$
$S_N$

Output

Print $N$ lines. The $i$-th $(i = 1, 2, \dots, N)$ line should contain $\displaystyle \max_{i \neq j} \mathrm{LCP}(S_i, S_j)$.

Sample Input 1

3
abc
abb
aac

Sample Output 1

2
2
1

$\mathrm{LCP}(S_1, S_2) = 2, \mathrm{LCP}(S_1, S_3) = 1$, and $\mathrm{LCP}(S_2, S_3) = 1$.

Sample Input 2

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

Sample Output 2

4
3
2
1
0
1
0
4
3
2
1

问题描述

给你$N$个由小写英文字母组成的字符串。令$S_i$表示第$i$个字符串，$i = 1, 2, \dots, N$。

对于两个字符串$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)$

限制条件

• $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$行应包含$\displaystyle \max_{i \neq j} \mathrm{LCP}(S_i, S_j)$，$i = 1, 2, \dots, N$。

样例输入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