← 返回题目列表

AtCoder · abc377_g

G. 编辑以匹配

中文机器翻译题面 查看原题

分数: 575 点

问题陈述

你被给予 N 字符串 S_1,S_2,\ldots,S_N。每个字符串由小写英文字母组成。

对于每个 k=1,2,\ldots,N,解决以下问题。

让 T=S_k 并考虑以任何顺序执行以下两种类型的操作任意次数:

  • 支付费用 1 删除最后一个字符 T。此操作可以在以下情况下进行: T 不为空。
  • 支付费用 1 在末尾添加任意小写英文字母 T.

找出制造所需的最小总成本 T 为空或匹配以下之一 S_1,S_2,\ldots,S_{k-1}.

约束

  • 1\le N\le 2\times 10^5
  • 每个 S_i 是长度至少为 1 由小写英文字母组成。
  • \displaystyle \sum_{i=1}^N |S_i|\le 2\times 10^5

输入

输入由标准输入按以下格式给出:

N
S_1
S_2
\vdots
S_N

输出

打印 N 行。 的 i第行 (1\le i\le N) 应包含以下问题的答案 k=i.


示例输入 1

3
snuke
snuki
snuuk

示例输出 1

5
2
4

对于 k=1,你可以使 通过执行删除操作五次将 T 清空。

对于 k=2,你可以使 通过执行删除操作五次将 T 匹配 S_1 删除最后一个字符然后添加 e 到最后。

对于 k=3,你可以使 通过执行删除操作五次将 T 匹配 S_2 删除最后一个字符两次,然后添加 k 到最后,最后添加 i 到最后。


示例输入 2

3
abc
arc
agc

示例输出 2

3
3
3

示例输入 3

8
at
atatat
attat
aatatatt
attattat
ttatta
tta
tt

示例输出 3

2
4
3
8
3
6
3
1