#P18865. [HONI 2013/2014 #1] SLASTIČAR
[HONI 2013/2014 #1] SLASTIČAR
题目描述
有一个长度为 的数字串 ,以及 个要检查的数字串。对每个待查串 ,机器人从 的第 个位置开始尝试匹配。设 长为 。
在尝试起点 时,机器人从左到右逐字符比较 的第 至 个位置与 。超出 末尾的位置视为字符 #。比较遇到第一个不同的字符时,结束这次尝试,并把起点加 。如果全部 个字符相同,则立即停止这次查询。如果试过全部 个起点都没有匹配,也停止查询。
每比较一对字符收费一克罗地亚库纳,包括发现不相同的那一次。对每个 ,求查询费用。
输入格式
第一行是 ,满足 。第二行是长度为 的数字串 。
第三行是 ,满足 。接下来 行各给一个非空数字串,长度不超过 。所有待查串长度之和不超过 。
输出格式
输出 行,第 行是查询第 个串的费用。
部分分
的分值满足 、,且每个待查串长不超过 。
样例
样例 1
输入
7
1090901
4
87650
0901
109
090
输出
7
10
3
4
样例 2
输入
10
5821052680
4
210526
2105
582
105268
输出
8
6
3
9
样例 3
输入
3
001
1
11
输出
4