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