题目详情题解（0）讨论（0）提交记录（0）

AT_abc287_e.[ABC287E] Karuta

普及+/提高

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

给定 NN 个由小写英文字母组成的字符串。第 ii 个字符串记为 SiS_i。

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

  • x,yx, y 的长度都不少于 nn。
  • 对于所有 1≤i≤n1 \leq i \leq n，xx 的第 ii 个字符与 yy 的第 ii 个字符相同。

对于每个 i=1,2,…,Ni = 1, 2, \dots, N，请你求出：

  • max⁡i≠jLCP(Si,Sj)\displaystyle\max_{i \neq j} \mathrm{LCP}(S_i, S_j)

输入格式

输入按以下格式从标准输入读入：

NN
S1S_1
S2S_2
⋮\vdots
SNS_N

输出格式

输出 NN 行。第 ii 行输出 max⁡i≠jLCP(Si,Sj)\displaystyle\max_{i \neq j} \mathrm{LCP}(S_i, S_j)。

输入输出样例

  • 输入#1

    3
abc
abb
aac

    输出#1

    2
2
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

说明/提示

限制条件

  • 2≤N≤5×1052 \leq N \leq 5 \times 10^5
  • NN 是整数
  • SiS_i 是由小写英文字母组成的字符串，长度至少为 11（i=1,2,…,Ni = 1, 2, \dots, N）
  • 所有 SiS_i 的长度之和不超过 5×1055 \times 10^5

样例解释 1

LCP(S1,S2)=2, LCP(S1,S3)=1, LCP(S2,S3)=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 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页