#P5684. [ABC287E] Karuta

[ABC287E] Karuta

题目描述

给定 NN 个字符串。对每个 ii,求出 SiS_i 与其他任意一个字符串的最长公共前缀长度的最大值。

max⁡j≠iLCP⁡(Si,Sj)\max_{j\ne i}\operatorname{LCP}(S_i,S_j)

其中 LCP(Si,Sj)\text{LCP}(S_i, S_j) 表示两字符串最长公共前缀的长度。

输入格式

第一行一个整数 NN。接下来 NN 行,每行一个字符串 SiS_i。

输出格式

输出 NN 行,第 ii 行给出对应 SiS_i 的答案。

样例 #1

样例输入 #1

3
abc
abb
aac

样例输出 #1

2
2
1

样例 #2

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

数据范围

2≤N≤5×1052\le N\le5\times10^5。每个字符串非空,且仅由小写英文字母组成。所有字符串长度之和不超过 5×1055\times10^5。

AtCoder 原题