#P10709. 孙笑川的家乡话

    ID: 9827 传统题 2000ms 64MiB 尝试: 2 已通过: 2 难度: 8 上传者: 标签>CF2400提高+/省选-根号分块卷积转化NTT直接模拟

孙笑川的家乡话

题目描述

给定长度为 NN 的二进制串 SS 和长度为 MM 的二进制串 TT。从 SS 的第 ii 个字符开始,把 TT 的各字符按顺序与 SS 中连续位置上的字符比较。

初始容忍度为 KK。比较 TT 的第 jj 个字符时,若两字符不同,则容忍度减少 fjf_j。减少后容忍度若小于 00,立刻停止,终止位置为当前比较的 SS 中位置。否则继续比较下一对字符。

若顺利读完 TT,终止位置为 i+Mi+M。若先读到了 SS 的末尾且尚未停止,终止位置为 N+1N+1。对每个起点 i=1,…,Ni=1,\ldots,N,求终止位置。

输入格式

第一行三个整数 N,M,KN,M,K。第二行长度为 NN 的二进制串 SS。第三行长度为 MM 的二进制串 TT。第四行 MM 个整数 f1,…,fMf_1,\ldots,f_M。

输出格式

输出一行 NN 个整数,第 ii 个表示从 SS 的第 ii 位开始时的终止位置。

样例 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

数据范围

所有数据满足 1≤N,M≤1051\le N,M\le10^5,0≤K≤1080\le K\le10^8,1≤fi≤1031\le f_i\le10^3。时间限制 22 秒,内存限制 6464 MB。

测试点 附加限制
1 N,M≤103N,M\le10^3
2–3 K=0K=0
4 K≤100K\le100
5–6 TT 的所有字符均为 1
7–10 无

原 PDF 题面