← 返回题目列表

Codeforces · 62/B

B. 廷德克斯·布罗姆

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

Tyndex 再次遥遥领先于竞争对手!对 Zoozle Chrome 浏览器发布的反应是新浏览器 Tyndex.Brome 的发布!

新浏览器的受欢迎程度与日俱增。秘密甚至不在于安装了 Tyndex.Bar(在您购买 Tyndex.Bottles 并将其插入 USB 端口后,Tyndex.Bar 会自动向玻璃杯中注入最好的 1664 干邑白兰地)。由于与用户的深思熟虑的互动,它非常受欢迎。

让我们以自动地址更正系统为例。您是否输入了 codehorses 而不是 codeforces?郁闷的Zoozle Chrome会悲伤地说该地址不存在。 Tyndex.Brome同时会自动找到最近的地址并将您发送到那里。太棒了!

这个出色的功能是如何工作的?很简单!对于每个潜在地址,F 误差的函数通过以下规则计算:

- 对于来自潜在地址 c 的每个字母 ci,找到用户输入的地址中字母 ci 最接近的位置 j。绝对差|i - j|因此,对于每个 i (1 ≤ i ≤ |c|),选择位置 j,使得 ci = sj,且 |i - j|是最小的可能。
- 如果用户输入的地址中不存在这样的字母ci,则潜在地址|c|的长度添加到F。

计算所有潜在地址的误差函数值后,找到最合适的地址。

为了更好地理解上述方法的特殊功能,建议实现针对用户给定的地址和一些潜在地址集计算F函数的算法。祝你好运!

输入

第一行包含两个整数 n 和 k (1 ≤ n ≤ 105, 1 ≤ k ≤ 105)。它们是潜在地址的数量和用户输入的地址的长度。下一行包含 k 个小写拉丁字母。它们是用户输入的地址。接下来的每个第 i (1 ≤ i ≤ n) 行包含一个非空的小写拉丁字母序列。它们是潜在的地址。保证所有线路的总长度不超过2·105。

输出

在输出文件的每 n 行上打印一个数字:选择当前潜在地址时的误差函数值。

请不要使用 %lld 说明符在 C++ 中读取或写入 64 位整数。最好使用 cout (也可以使用 %I64d)。

示例

输入 #1

2 10
codeforces
codeforces
codehorses

输出 #1

0
12

输入 #2

9 9
vkontakte
vcontacte
vkontrakte
vkollapse
vkrokodile
vtopke
vkapuste
vpechke
vk
vcodeforcese

输出 #2

18
14
36
47
14
29
30
0
84