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

AT_abc377_g.[ABC377G] Edit to Match

提高+/省选-

通过率：0%

AC君温馨提醒

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

题目描述

给你 NN 个字符串 S1,S2,…,SNS_1,S_2,\ldots,S_N 。每个字符串都由小写英文字母组成。

对于每一个 k=1,2,…,Nk=1,2,\ldots,N，解决下列问题：

一开始将一个字符串 TT 赋为 SkS_k。

接下来，你可以在下列操作中二选一，并可以操作无限次。但每一次操作都会花费 11 的代价。

  • 当 TT 不为空时，删除 TT 的最后一个字符。
  • 在 TT 后面加上一个任意的小写字母。

求使 TT 要么为空，要么与 S1,S2,…,Sk−1S_1,S_2,\ldots,S_{k-1} 中的一个匹配所需的最小代价。

输入格式

第一行一个正整数 NN。

第 22 至 N+1N+1 行，每行一个字符串 SiS_i。

输出格式

共 NN 行。第 ii 行输出当 k=ik=i 时的最小代价。

输入输出样例

  • 输入#1

    3
snuke
snuki
snuuk

    输出#1

    5
2
4

  • 输入#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

说明/提示

  • 1≤N≤2×1051\le N\le 2\times10^5
  • ∑i=1N∣Si∣≤2×105\sum\limits_{i=1}^N|S_i|\le2\times10^5

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

首页