题目详情
返回题库题目描述
给你N个字符串$ S_1,S_2,…,S_N $。每个字符串都由小写英文字母组成。
请为每个k=1,2,…,N解决下面的问题。
设T=$S_k$并考虑以任意顺序执行以下两种类型的操作任意多次：
- 花费1删除T的最后一个字符。当T不为空时，可以进行此操作。
- 支付1的代价，在T的末尾添加任何小写英文字母。
- 求使T要么为空，要么与$S_1,S_2,…,S_{k-1}$中的一个匹配所需的最小总成本。
输入描述
数据范围：
- 1≤N≤2×$10^5$
- 每个字符串中只包含小写字母
- $\sum_{i=1}^{N}$∣Si∣≤2×$10^5$
输出描述
输出N行。每行代表第i个答案
提示
样例1：
对于k=1，执行五次删除操作即可将T清空。
对于k=2，可以通过删除最后一个字符，然后在末尾添加e使T与S1匹配。
对于k=3，可以通过删除最后一个字符两次，然后在末尾添加k，最后在末尾添加i，使T与S2相匹配。