分数: 500 点
问题陈述
你被给予 N 由小写英文字母组成的字符串。 让 其中 S_i 是 i-th (i = 1, 2, \dots, N) 。
对于两个字符串 x 和 y, \mathrm{LCP}(x, y) 被定义为最大整数 n 满足以下所有条件:
- 的长度 x 和 y 至少都是 n.
- 对于所有整数 i 之间 1 和 n,包含在内, i- 第一个字符 x 以及 y 相等。
查找所有值的以下值 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-th (i = 1, 2, \dots, N) 行应包含 \displaystyle \max_{i \neq j} \mathrm{LCP}(S_i, S_j).
示例输入 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