#P10709. 孙笑川的家乡话
孙笑川的家乡话
题目描述
给定长度为 的二进制串 和长度为 的二进制串 。从 的第 个字符开始,把 的各字符按顺序与 中连续位置上的字符比较。
初始容忍度为 。比较 的第 个字符时,若两字符不同,则容忍度减少 。减少后容忍度若小于 ,立刻停止,终止位置为当前比较的 中位置。否则继续比较下一对字符。
若顺利读完 ,终止位置为 。若先读到了 的末尾且尚未停止,终止位置为 。对每个起点 ,求终止位置。
输入格式
第一行三个整数 。第二行长度为 的二进制串 。第三行长度为 的二进制串 。第四行 个整数 。
输出格式
输出一行 个整数,第 个表示从 的第 位开始时的终止位置。
样例 1
7 6 1
1101110
110011
1 1 4 5 1 3
4 4 5 6 8 8 8
样例 2
20 10 15
10011111001101010110
1011110101
2 1 4 7 4 8 3 6 4 7
11 12 13 13 11 13 17 15 19 15 20 18 20 21 21 21 21 21 21 21
数据范围
所有数据满足 ,,。时间限制 秒,内存限制 MB。
| 测试点 | 附加限制 |
|---|---|
| 1 | |
| 2–3 | |
| 4 | |
| 5–6 | 的所有字符均为 1 |
| 7–10 | 无 |