B. Tyndex.Brome
Tyndex。布罗姆
每次测试的时间限制
2秒
每次测试的内存限制
256字节
输入
标准输入
输出
标准输出
Tyndex再次遥遥领先于竞争对手!Zoozle Chrome浏览器发布后的反应是发布了一个新的浏览器Tyndex.Brome!
这种新浏览器的受欢迎程度与日俱增。秘密甚至都不是泰dex。Bar安装(Tyndex。在你购买Tyndex后，酒吧会自动为你斟满最好的1664年干邑。瓶子和插入USB端口)。它非常受欢迎，因为它与用户的互动是经过深思熟虑的。
让我们以自动地址更正系统为例。您是否输入了码马而不是码力?阴郁的Zoozle Chrome浏览器会悲伤地说这个地址不存在。Tyndex。Brome同时会自动找到最近的地址并把你送到那里。这是辉煌!
这个奇妙的函数是如何工作的呢?这是简单的!对于每个潜在地址，F误差的函数按以下规则计算:
对于来自潜在地址c的每个字母ci，找到用户输入的地址中字母ci最近的位置j。这些位置的绝对差|i-j|被加到f中，因此对于每一个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)。
time limit per test
2 seconds
memory limit per test
256 megabytes
Tyndex is again well ahead of the rivals! The reaction to the release of Zoozle Chrome browser was the release of a new browser Tyndex.Brome!
The popularity of the new browser is growing daily. And the secret is not even the Tyndex.Bar installed (the Tyndex.Bar automatically fills the glass with the finest 1664 cognac after you buy Tyndex.Bottles and insert in into a USB port). It is highly popular due to the well-thought interaction with the user.
Let us take, for example, the system of automatic address correction. Have you entered
codehorses instead of
codeforces? The gloomy Zoozle Chrome will sadly say that the address does not exist. Tyndex.Brome at the same time will automatically find the closest address and sent you there. That's brilliant!
How does this splendid function work? That's simple! For each potential address a function of the
F error is calculated by the following rules:
-
for every letter ci from the potential address c the closest position j of the letter ci in the address (s) entered by the user is found. The absolute difference |i-j| of these positions is added to F. So for every i (1≤i≤|c|) the position j is chosen such, that ci=sj, and |i-j| is minimal possible.
-
if no such letter ci exists in the address entered by the user, then the length of the potential address |c| is added to F.
After the values of the error function have been calculated for all the potential addresses the most suitable one is found.
To understand the special features of the above described method better, it is recommended to realize the algorithm of calculating the
F function for an address given by the user and some set of potential addresses. Good luck!
Output
On each
n line of the output file print a single number: the value of the error function when the current potential address is chosen.
Please, do not use
%lld specificator to read or write 64-bit integers in C++. It is preffered to use
cout (also you may use
%I64d).
Examples
Output
18
14
36
47
14
29
30
0
84