分数: 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