编辑到匹配

题目描述

给定 $N$ 个字符串 $S_1, S_2, \dots, S_N$。每个字符串由小写英文字母组成。

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

设 $T = S_k$，考虑按任意顺序、任意次数进行以下两种操作：

• 支付 $1$ 的费用删除 $T$ 的最后一个字符。当 $T$ 非空时可以进行该操作。
• 支付 $1$ 的费用在 $T$ 的末尾添加任意一个小写英文字母。

求使 $T$ 变为空字符串或与 $S_1, S_2, \dots, S_{k-1}$ 中某一个字符串一致所需的最小总费用。

输入格式

输入按以下格式从标准输入给出：

$N$
$S_1$
$S_2$
$\vdots$
$S_N$

输出格式

输出 $N$ 行。 第 $i$ 行（$1 \le i \le N$）输出 $k = i$ 时的答案。

样例

3
snuke
snuki
snuuk

5
2
4

对于 $k = 1$，执行五次删除操作即可使 $T$ 变为空。

对于 $k = 2$，先删除最后一个字符，再在末尾添加 e，即可使 $T$ 与 $S_1$ 一致。

对于 $k = 3$，先删除两次最后一个字符，再依次在末尾添加 k 和 i，即可使 $T$ 与 $S_2$ 一致。

3
abc
arc
agc

3
3
3

8
at
atatat
attat
aatatatt
attattat
ttatta
tta
tt

2
4
3
8
3
6
3
1

数据范围

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